力扣30. 串联所有单词的子串

描述

力扣 30. 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]，那么“abcdef”，“abefcd”，“cdabef”，“cdefab”，“efabcd”，和“efcdab”都是串联子串。“acdbef”不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s =“barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串“barfoo”开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串“foobar”开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：
输入：s =“wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：
输入：s =“barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串“foobarthe”开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串“barthefoo”开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串“thefoobar”开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

提示：
1 1 1 words[i] 和 s 由小写英文字母组成

方法：动态规划

思路：
遍历 + 滑动窗口解决。字串的长度一样且全部都需要用上。我们可以将 s 字符串进行切割，个数即为子串数组的个数，长度即为子串单个字符串的长度。切割后再利用 HashMap 进行比对。并且我们只需要遍历子串长度次即可解决。比如对于字符串 s =“mapcathat…”，我们第一次从 m 开始，第二次从 a 开始，第三次从 p 开始。就不用再从 c 开始进行第四次遍历了，因为从 m 开始包含了从 c 开始。
具体实现及注释：

class Solution {
   public ListInteger> findSubstring(String s, String[] words) {
       ListInteger> ans = new ArrayList(); 
       
       int sLength = s.length();
       
       int wordsNum = words.length;
       
       int wLength = words[0].length();
       
       if (sLength  wordsNum * wLength) return ans;
       
       int end = sLength - wordsNum * wLength;
       for (int i = 0; i  wLength && i  end; i++) {
           
           HashMapString, Integer> mp = new HashMap>();
           int count = wordsNum;
           int index = i;
           
           while (count != 0) {
               String word = s.substring(index, index+wLength);
               mp.put(word, mp.getOrDefault(word, 0) + 1);
               count--;
               index += wLength;
           }
           
           for (String word : words) {
               mp.put(word, mp.getOrDefault(word, 0) - 1);
               
               if (mp.get(word) == 0) mp.remove(word);
           }
           index = i + wLength;
           
           if (mp.isEmpty()) ans.add(i); 
           
           while (index  end) {
               String word1 = s.substring(index-wLength, index);
               mp.put(word1, mp.getOrDefault(word1, 0) - 1);
               if (mp.get(word1) == 0) mp.remove(word1);
               String word2 = s.substring(index+(wordsNum-1)*wLength, index+wordsNum*wLength);
               mp.put(word2, mp.getOrDefault(word2, 0) + 1);
               if (mp.get(word2) == 0) mp.remove(word2);
               if (mp.isEmpty()) ans.add(index);
               index += wLength;
           }

       }
       return ans;
   }
}