資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中查詢字串中的所有字謎
假設我們有一個字串 s 和一個非空字串 p，我們需要找到 p 的所有字謎在 s 中的起始索引。字串僅包含小寫字母，並且字串 s 和 p 的長度都不會大於 20 和 100。例如，如果 s：“cbaebabacd” p：“abc”，則輸出將為 [0, 6]，在索引 0 處，它是“cba”，另一個是“bac”，這些都是“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 時，
如果 s[left] 不存在於 m 中，則將 counter 加 1，並將 m[s[left]] 加 1
將 left 加 1
如果 m 包含 s[right] 且 m[s[right]] 不為零，則將 right 減 1，並退出迴圈
如果 m 不包含 s[left]，則設定 left := right + 1
返回 ans
示例（C++）
讓我們看看下面的實現來更好地理解：
#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("cbaebabacd", "abc")) ;
}輸入
"cbaebabacd" "abc"
輸出
[0, 6, ]
更新於：2020-04-29
2K+ 瀏覽量
廣告