串联所有单词的子串

题目链接

串联所有单词的子串

题目描述

注意点

• words[i] 和 s 由小写英文字母组成
• 1 <= words.length <= 5000
• 可以以 任意顺序 返回答案
• words中所有字符串长度相同

解答思路

• 根据滑动窗口+哈希表解决本题，哈希表存储words中所有的单词及单词的出现次数，滑动窗口时使用另一个哈希表存储当前窗口内已经出现的单词及单词的出现次数
• 因为words中所有字符串长度相同，所以在移动滑动窗口右边界时应该以单词为维度，每次移动wordLen个单位，然后判断该部分单词rightWord是否能作为串联串联所有单词的子串的一部分，有以下三种情况：
  • 如果rightWord根本不属于words中的单词，说明包含该单词时的子串一定不满足题意，此时需要将滑动窗口直接移动到该单词右侧，也就是直接重置滑动窗口的左右边界
  • 如果rightWord属于words中的单词，但是当前滑动窗口中该单词数量已经达到words中该单词的最大数量，此时需要移动滑动窗口的左边界，移动时每次也同样移动wordLen个单位，直到左侧找到一个与rightWord相同的值leftWord（一定能找到），将滑动窗口左边界移动到leftWord右侧
  • 如果rightWord属于words中的单词，且当前滑动窗口中该单词数量还未超过words中该单词的最大数量，此时满足题意，继续移动滑动窗口右边界（注意判断该滑动窗口已经是串联所有单词的子串的情况）
• 上述过程并未判断所有情况，因为每次移动边界时都是以wordLen为单位，如果从字符串首位置开始，可能会忽略1,2…(wordLen - 1)为起始位置的情况，观察规律可得，只需要对1,2…(wordLen - 1)为起始位置都执行一次上述的操作就可以考虑到所有的情况

代码

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<>();int wordSum = words.length;int wordLen = words[0].length();if (s.length() < wordSum * wordLen) {return res;}Map<String, Integer> map = new HashMap<>();for (String word : words) {map.put(word, map.getOrDefault(word, 0) + 1);}for (int i = 0; i < wordLen; i++) {int left = i;int right = i;int currWordSum = 0;Map<String, Integer> visitedMap = new HashMap<>();while (right + wordLen <= s.length()) {// 长度越界，剩下的子串一定无法串联所有单词if (left + (wordSum - currWordSum) * wordLen > s.length()) {break;}String leftWord = s.substring(left, left + wordLen);String rightWord = s.substring(right, right + wordLen);// 该单词不存在，则有该单词的部分都一定不满足题意，将滑动窗口左边界移动至该单词右侧if (map.get(rightWord) == null) {left = right + wordLen;visitedMap = new HashMap<>();currWordSum = 0;}// 该单词存在但words中已经没有该单词if (map.get(rightWord) != null && visitedMap.getOrDefault(rightWord, 0) >= map.get(rightWord)) {while (left < right && !rightWord.equals(leftWord)) {visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);left += wordLen;leftWord = s.substring(left, left + wordLen);currWordSum--;}left += wordLen;}// 该单词存在满足题意if (map.get(rightWord) != null && visitedMap.getOrDefault(rightWord, 0) < map.get(rightWord)) {visitedMap.put(rightWord, visitedMap.getOrDefault(rightWord, 0) + 1);currWordSum++;// 已找到串联所有单词的子串if (currWordSum == wordSum) {res.add(left);visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);currWordSum--;left += wordLen;}}right += wordLen;}}return res;}
}

关键点

• 滑动窗口的思想
• 移动滑动窗口时其对应的哈希表的变化
• 移动滑动窗口右边界时对应单词是否是串联所有单词的子串的三种情况