一、題目內容
給定一個字串 s 和一個非空字串 p，找到 s 中所有是 p 的字母異位詞的子串，回傳這些子串的始索引，字串只包含小寫英文字母，并且字串 s 和 p 的長度都不超過 20100，
說明：
- 字母異位詞指字母相同，但排列不同的字串，
- 不考慮答案輸出的順序，
示例1：
輸入:s: "cbaebabacd" p: "abc"
輸出:[0, 6]
解釋: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞，起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞示例2：
輸入:s: "abab" p: "ab"
輸出:[0, 1, 2]
解釋:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞，起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異詞，起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞，
二、題目分析
直接套用之前的模式，使用雙指標來模擬一個滑動視窗進行解題，分析程序如下：
假設我們有字串為“cbaebabacd”，目標串為“abc”
我們通過雙指標維護一個視窗，由于我們只需要判斷字母異位詞，我們可以將視窗初始化大小和目串保持一致，（當然，你也可以初始化視窗為1，逐步擴大）
而判斷字母異位詞，我們需要保證視窗中的字母出現次數與目標串中的字母出現次數一致，這里因字母只有26個，直接使用陣列來替代map進行存盤（和上一講中的ASCII使用256陣列存盤思想一致），
pArr為目標串陣列，sArr為視窗陣列，我們發現初始化陣列，本身就滿足，記錄下來，（這里圖示用map模擬陣列，便于理解）
然后我們通過移動視窗，來更新視窗陣列，進而和目標陣列匹配，匹配成功進行記錄，每一次視窗移動，左指標前移，原來左指標位置處的數值減1，表示字母移出；同時右指標前移，右指標位置處的數值加1，表示字母移入，詳細程序如下：
三、代碼實作
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return new ArrayList<>();
List<Integer> list = new ArrayList<>();
int[] pArr = new int[26];
int pSize = p.length();
int[] sArr = new int[26];
for (int i = 0; i < p.length(); i++) {
sArr[s.charAt(i) - 'a']++;
pArr[p.charAt(i) - 'a']++;
}
for (int i = 0; i < p.length(); i++) {
int index = p.charAt(i) - 'a';
if (pArr[index] == sArr[index])
pSize--;
}
int i = 0;
int j = p.length();
// 視窗大小固定為p的長度
while (j < s.length()) {
if (isSame(pArr, sArr))
list.add(i);
//sArr[s.charAt(i) - 'a']-- 左指標位置處字母減1
sArr[s.charAt(i) - 'a']--;
i++;
//sArr[s.charAt(j) - 'a']++ 右指標位置處字母加1
sArr[s.charAt(j) - 'a']++;
j++;
}
if (isSame( pArr, sArr))
list.add(i);
return list;
}
public boolean isSame(int[] arr1, int[] arr2) {
for (int i = 0; i < arr1.length; ++i)
if (arr1[i] != arr2[i])
return false;
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254003.html
標籤：其他
上一篇：2020博客之星評選收官詞
下一篇：用MATLAB設計FIR濾波器