力扣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，执行时间加快了一个量级。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是利用"窗口"这一概念，优化的时候可以利用题目本身的特殊性。