Sliding Window - 30. Substring with Concatenation of All Words

30. Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []

思路：

利用一个map，单词作为map的key，value是单词在words数组中出现的次数。然后去遍历s数组，使用两个指针，一个指针i作为查找单词的起始点，另一个作为单词长度的移动指针，这样在两个指针之间去用另一个哈希表copy来记录相同单词长度的单词和map之间的关系，如果出现map中没有的单词就移动指针i，进行下一轮查找比对。

代码：

java：

class Solution {

   /*public List<Integer> findSubstring(String s, String[] words) {

        if (s == null || words == null || s.length() == 0 || words.length == 0)
            return new ArrayList<>();
        
        List<Integer> res = new ArrayList<>();
        int n = words.length, m = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        
        // 记录下word中的String的出现次数
        for (String str : words) map.put(str, map.getOrDefault(str, 0) + 1);
        
        for (int i = 0; i <= s.length()- n*m; i++) {
            HashMap<String, Integer> copy = new HashMap<>(map);
            int k = n, j = i;
            while(k > 0) {
                String str = s.substring(j, j + m);
                if (!copy.containsKey(str) || copy.get(str) < 1) break;
                copy.put(str, copy.get(str) - 1);
                k--;
                j += m;
            }
            if (k == 0) res.add(i);
        }
        
        return res;
    }*/
    
     public List<Integer> findSubstring(String s, String[] words) {
         List<Integer> res = new ArrayList<>();
         if (s.length() == 0 || words.length == 0 || s.length() < words.length * words[0].length()) {
             return res;
         }
         
         int wordsLen = words.length, wlen = words[0].length();
         Map<String,Integer> map = new HashMap<>();
         
         // 记录word中单词出现的次数
         for(String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
         
         // 从单词每一位开始遍历
         for (int i = 0; i < wlen; i++) {
             // 然后按照单词的长度一个单词一个单词的寻找
             for (int j = i; j <= s.length() - wordsLen * wlen; j +=wlen) {
                 // 寻找匹配的字串
                 Map<String,Integer> temp = new HashMap<>();
                 for (int k = wordsLen - 1; k >= 0; k--) {
                     String t = s.substring(j + k * wlen, j + (k + 1) * wlen);
                     int val = temp.getOrDefault(t, 0) + 1;
                     if (val > map.getOrDefault(t, 0)) {
                         j += k * wlen;  // 如果出现map中没有的单词，就直接从下一个窗口起始点开始寻找
                         break;
                     }
                     
                     temp.put(t, val);
                     if (k == 0) res.add(j);
                 }
             }
         }
         
         return res;
     }
}```