力扣438——找到字符串中所有字母異位詞

2020 年 2 月 19 日
筆記

這道題主要是利用"窗口"這一概念，優化的時候可以利用題目本身的特殊性。

原題

給定一個字符串 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" 的字母異位詞。

原題url：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

解題

利用"窗口"思想

這道題類似字符串完全匹配，只是這道題要求連續但順序可以不一致。這樣就無法利用待匹配字符串預先構造了。

那麼結合這道題，為了能夠讓我們知道當前字符是否在待匹配字符串中，我們需要一個集合存儲。

為了能夠讓我們知道各個字符出現了幾次，我們需要一個哈希表，並且實時更新其次數，如果次數為0，則移除該項，如果哈希表為空，則說明找到了，記錄開始下標，並且窗口滑動。

結合上面的思路，我們可以寫出代碼：

class Solution {      public List<Integer> findAnagrams(String s, String p) {          // 最終結果          List<Integer> result = new LinkedList<>();          if (s == null || s.length() == 0) {              return result;          }          // 根據p構造map，key代表字符，value代表相應次數          Map<Character, Integer> map = new HashMap<>();          for (Character character : p.toCharArray()) {              map.put(character, map.getOrDefault(character, 0) + 1);          }          // p中所有的字符          Set<Character> pCharSet = new HashSet<>(map.keySet());          // 每個字母出現的位置，value表示每一次出現的下標          Map<Character, LinkedList<Integer>> indexMap = new HashMap<>();          // 開始的下標          int first = 0;          char[] sArray = s.toCharArray();          // 遍歷s          for (int i = 0; i < sArray.length; i++) {              Character character = sArray[i];              // 如果character不在pCharSet中，說明該字符不存在              if (!pCharSet.contains(character)) {                  // 則重新構造indexMap                  indexMap = new HashMap<>();                  // 從first位置到i位置，還原map                  for (int j = first; j < i; j++) {                      character = sArray[j];                      map.put(character, map.getOrDefault(character, 0) + 1);                  }                  // 重置first的位置                  first = i + 1;                  continue;              }                // 從indexMap中獲取該字符出現的位置              LinkedList<Integer> indexList = indexMap.computeIfAbsent(character, k -> new LinkedList<>());              // 在末尾記錄當前位置              indexList.add(i);              // map中相應字符剩餘出現次數              Integer count = map.get(character);              // 如果次數為null，說明無法再減              if (count == null) {                  // 從開始下標到該字符第一次出現的下標，還原map和indexMap                  int firstIndex = indexList.removeFirst();                  for (int j = first; j < firstIndex; j++) {                      character = sArray[j];                      map.put(character, map.getOrDefault(character, 0) + 1);                      indexMap.get(character).removeFirst();                  }                  // 重置first的位置                  first = firstIndex + 1;                  continue;              }                // 次數-1              count--;              // 如果次數不為0，則重新放進map中              if (count > 0) {                  map.put(character, count);                  continue;              }                // 如果次數減為0，則移除該項              map.remove(character);              // 檢查map是否為空              if (!map.isEmpty()) {                  continue;              }                // 如果為空，說明滿足條件，記錄進result中              result.add(first);              // first向後移動1個（窗口滑動）              character = sArray[first];              map.put(character, map.getOrDefault(character, 0) + 1);              indexMap.get(character).removeFirst();              first++;          }            return result;      }  }

提交OK，但執行用時很慢，需要優化。

優化

上面解法查詢慢，我感覺根本原因在於使用了比較複雜的數據結構，包括集合、哈希表、鏈表等，雖然 Java 中針對這些結構做了優化，但相比於最基礎的結構數組而言，在查找和更新上還是更慢了。這道題可以用數組的主要原因在於只會出現26個小寫英文字母。這樣用了數組之後，查找和更新都快了太多。大家可以根據這個思路優化試試。

既然有提到窗口，那麼我們就將這個思想用到極致。可以先將窗口設置的大一些，比如至少包含目標字符串里的所有字符。達成條件後，就開始把左邊開始縮小，直到縮小成目標字符串的長度後，然後記錄進結果中，之後窗口右移，重複上述過程。

接下來看看代碼：

class Solution {      public List<Integer> findAnagrams(String s, String p) {          if(s == null || s.length() == 0) return new ArrayList<>();          List<Integer> res = new ArrayList<>();          // 需要的字符，由於都是小寫字母，因此直接用26個長度的數組代替原來的HashMap          int[] needs = new int[26];          for(char ch : p.toCharArray()) {              needs[ch - 'a'] ++;          }          // "窗口"          int[] window = new int[26];          // 窗口的左右下標          int left = 0, right = 0;          // 用total檢測窗口中是否已經涵蓋了p中的所有字符          int total = p.length();          // 遍歷s          while(right < s.length()) {              char chr = s.charAt(right);              // 如果該字符在p中出現過              if(needs[chr - 'a'] > 0) {                  // 則在窗口中記下該字符                  window[chr - 'a'] ++;                  // 如果當前窗口中該字符的數量，小於需要的數量                  if(window[chr - 'a'] <= needs[chr - 'a']) {                      // 則total數量減1                      total --;                  }              }              // total為0，說明窗口中包含了p中所有字符              while(total == 0) {                  // (right - left + 1)代表窗口的大小                  // 如果窗口的大小等於p，說明符合要求                  if(right - left + 1 == p.length()){                      // 記錄左指針                      res.add(left);                  }                  // 左指針向右移動1個                  char chl = s.charAt(left);                  left ++;                  // 如果左指針屬於p中                  if(needs[chl - 'a'] > 0) {                      // 那麼窗口中該字符的數量也需要減1                      window[chl - 'a'] --;                      // 如果窗口中該字符的數量小於需要的數量                      if(window[chl - 'a'] < needs[chl - 'a']) {                          // 則total加1，跳出循環，說明還需要繼續向右尋找                          total ++;                      }                  }              }              // 繼續向右尋找              right ++;          }          return res;      }  }

提交OK，執行時間加快了一個量級。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是利用"窗口"這一概念，優化的時候可以利用題目本身的特殊性。