資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢字串T中字串S所有異位詞的起始索引
假設我們有兩個字串S和T，我們需要找到S的所有異位詞在T中的所有起始索引。字串只包含小寫字母，並且字串S和T的長度都不會超過20和100。
因此，如果輸入類似於S = "cab" T = "bcabxabc"，則輸出將為[0, 1, 5]，因為子字串"bca"、"cab"和"abc"。
為了解決這個問題，我們將遵循以下步驟
定義一個對映m，n := s的長度，設定left := 0，right := 0，counter := p的長度
定義一個數組ans
將p中字元的頻率儲存到對映m中
對於right := 0 到 n – 1
如果m包含s[right]且m[s[right]]不為零，則將m[s[right]]減少1，將counter減少1，如果counter = 0，則將left插入ans
否則
當left < right時，
如果m中不存在s[left]，則將counter增加1，並將m[s[left]]增加1
將left增加1
如果m包含s[right]且m[s[right]]不為零，則將right減少1，並退出迴圈
如果m不包含s[left]，則設定left := right + 1
返回ans
讓我們看看下面的實現以更好地理解
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
map <char, int> m;
int n = s.size();
int left = 0, right = 0;
int counter = p.size();
vector <int> ans;
for(int i = 0; i < p.size(); i++) m[p[i]]++;
for(int right = 0; right < n; right++){
if(m.find(s[right]) != m.end() && m[s[right]]){
m[s[right]]--;
counter--;
if(counter == 0)ans.push_back(left);
} else {
while(left<right){
if(m.find(s[left]) != m.end()) {
counter++;
m[s[left]]++;
}
left++;
if(m.find(s[right]) != m.end() && m[s[right]]){
right--;
break;
}
}
if(m.find(s[left])==m.end())left = right + 1;
}
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.findAnagrams("bcabxabc", "cab")) ;
}輸入
"bcabxabc", "cab"
輸出
[0, 1, 5, ]
更新於: 2020年11月9日
157 次瀏覽
廣告