leetcode|困难:30. 串联所有单词的子串

1.题目

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

2. 题解

2.1 思路分析

思路1：滑动窗口+词频统计
    对words进行词频统计 
    然后以words包含的所有字符数作为窗口大小进行滑动+窗口词频统计
    判断词频是否相等并记录相对的位置
思路2：#TODO
    借鉴KMP对思路1进行优化 避免进行一些冗余比较

2.2 代码实现

• 思路1：滑动窗口+词频统计

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();

        // 记录下来每个单词的长度和单词的总长度
        int wordLen = words[0].length();
        int allWordLen = words.length*wordLen;

        // 统计words的词频
        Map<String,Integer> wordFrequnce = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if(!wordFrequnce.containsKey(words[i])) {
                wordFrequnce.put(words[i], 1);
            }else {
                wordFrequnce.replace(words[i], wordFrequnce.get(words[i])+1);
            }
        }

        // 采用滑动窗口进行遍历,每次滑动一个字符
        for (int i = 0; i <= s.length()-allWordLen; i++) {
            // 统计滑动窗口内的词频
            Map<String,Integer> winWordFrequnce = new HashMap<>();
            for (int j = 0; j < allWordLen; j+=wordLen) {
                String tmpWord = s.substring(i+j,i+j+wordLen);
                if(!winWordFrequnce.containsKey(tmpWord)) {
                    winWordFrequnce.put(tmpWord, 1);
                }else {
                    winWordFrequnce.replace(tmpWord, winWordFrequnce.get(tmpWord)+1);
                }
            }
            // 判断二者的词频是否一致
            boolean sameFlag = winWordFrequnce.equals(wordFrequnce);

            // 将开始所以加入到res
            if(sameFlag){
                res.add(i);
            }
        }
        return res;
    }
}

2.3 提交结果

参考资料

1. https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words