推 pandix: 大師 02/05 12:35
推 SecondRun: 跟昨天那題好像 02/05 12:39
※ 編輯: Rushia (122.100.75.86 臺灣), 02/05/2023 12:42:14
438. Find All Anagrams in a String
給你一個字串s和p，若s的某個子字串可以由p的字元排列後得到，返回s的子字串第一個
字元的索引值。
Example :
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
s[0:2]="cba" 可以被p組合所以加入0
s[6:8]="bac" 可以被p組合所以加入6
思路：
1.首先，若p的長度大於s則必不存在解，所以可以直接返回。
2.因為p可以任意排列所以我們只關心他的字母數量，我們可以維護一個基於s的
滑動窗口，每次加入一個元素，如果s的字母數量大於p就把最左邊的字母從窗口
去除並更新窗口左邊界，直到窗口的字母數量小於等於目標數量。
3.如果窗口的大小剛好等於p那就表示有一個子字串滿足條件，將left加入結果集，
當右邊的指標跑完s就可以得到解了。
Java Code：
---------------------------------------
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s.length() < p.length()) {
return res;
}
int[] target = new int[26];
for (char c : p.toCharArray()) {
target[c - 'a']++;
}
int left = 0, right = 0;
int [] window = new int[26];
while (right < s.length()) {
char c = s.charAt(right);
window[c - 'a']++;
while (window[c - 'a'] > target[c - 'a']) {
char first = s.charAt(left);
window[first - 'a']--;
left++;
}
if (right - left + 1 == p.length()) {
res.add(left);
}
right++;
}
return res;
}
}
---------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675571641.A.8FD.html