30. 串联所有单词的子串

题解链接：https://leetcode.wang/leetCode-30-Substring-with-Concatenation-of-All-Words.html

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        // HashMap1存储所有单词
        Map<String, Integer> allWords = new HashMap<>();
        for (String w : words) {
            allWords.put(w, allWords.getOrDefault(w, 0) + 1);
        }
        // 遍历所有子串
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            // HashMap2存储当前扫描的字符串含有的单词
            Map<String, Integer> hasWords = new HashMap<>();
            int num = 0;
            // 判断该子串是否符合
            while (num < wordNum) {
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                // 判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    hasWords.put(word, hasWords.getOrDefault(word, 0) + 1);
                    // 判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            // 判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;
    }
}

• 时间复杂度 O(m * n)，s 的长度为 n ，words 里有 m 个单词
• 空间复杂度 O(m)，words 里有 m 个单词