題目鏈接
串聯所有單詞的子串
題目描述
注意點
- 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;}
}
關鍵點
- 滑動窗口的思想
- 移動滑動窗口時其對應的哈希表的變化
- 移動滑動窗口右邊界時對應單詞是否是串聯所有單詞的子串的三種情況
