找到字元串中所有字母異位詞
找到字元串中所有字母異位詞
作者：Grey
原文地址：找到字元串中所有字母異位詞
題目描述
主要思路
使用滑動窗口和欠賬表的機制，首先，將p串建立詞頻表
int c = pStr.length;
for (char ch : pStr) {
map[ch - 'a']++;
}
用於查詢s串中還欠p串的元素種類和個數是多少。總共欠的字元個數是c。
接下來建立滑動窗口，在s串中設置l和r兩個指針，先移動r，如果r位置的字元正好是p中的字元，說明這是一次有效還款，則c--，r繼續移動，如果每次都是有效還款，則c必減為0，此時，就可以收集答案了，當r - l的長度正好是p串的長度時候，則說明必須以l位置的窗口，已經判斷完畢了，接下來，可以移動l指針，開始縮窗口。如果l縮的位置正好是有效位置，則c++（因為l的舊位置已經不屬於當前窗口了）。
時間複雜度O(N)。
完整程式碼
public class LeetCode_0438_FindAllAnagramsInAString {
// 滑動窗口 + 欠賬表
public List<Integer> findAnagrams(String s, String p) {
if (s == null || p == null) {
return new ArrayList<>();
}
List<Integer> ans = new ArrayList<>();
char[] str = s.toCharArray();
char[] pStr = p.toCharArray();
// 詞頻表
int[] map = new int[26];
// 窗口從[l,r)
int l = 0;
int r = 0;
// 欠賬數量
int c = pStr.length;
for (char ch : pStr) {
map[ch - 'a']++;
}
int n = str.length;
while (r < n) {
if (map[str[r] - 'a'] > 0) {
// 有效還款
c--;
}
map[str[r++] - 'a']--;
if (c == 0) {
// 收集到一個位置
ans.add(l);
}
// 形成窗口
if (r - l == pStr.length) {
// l面臨要出窗口
if (map[str[l] - 'a'] >= 0) {
// 退回去
c++;
}
map[str[l++] - 'a']++;
}
}
return ans;
}
}
