30. 串联所有单词的子串

题目：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

代码：

class Solution {

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        //每个单词出现的次数，即词频
        Map<String, Integer> wordsMap = new HashMap<>();
        //子串长度
        int subLen = 0;
        //统计词频和子串长度
        for (String w : words) {
            subLen += w.length();
            if (wordsMap.containsKey(w)) {
                wordsMap.put(w, wordsMap.get(w) + 1);
            }else{
                wordsMap.put(w, 1);
            }
        }
        //滑块遍历
        for (int i = 0; i <= s.length() - subLen; i++) {
            String sub = s.substring(i, i+subLen);
            if (this.matching(sub, wordsMap)) {
                res.add(i);
            }
        }

        return res;
    }

    /**
     * 匹配函数
     * @param sub
     * @param wordsMap
     * @return
     */
    private boolean matching(String sub, Map<String, Integer> wordsMap) {
        int len = 0;
        //字串的词频map
        Map<String, Integer> subMap= new HashMap<>();
        for (String word : wordsMap.keySet()) {
            subMap.put(word, 0);
            len = word.length();
        }
        //每个单词长度一定，拆分字符串s
        for (int i = 0; i < sub.length()/len; i++) {
            String word = sub.substring(i * len, (i+1) * len);
            if (wordsMap.get(word) == null) {
                //单词串中没有这个单词，不匹配
                return false;
            } else if (subMap.get(word)+1 > wordsMap.get(word)) {
                //word的词频已经大于要求，不匹配
                return false;
            }
            subMap.put(word,subMap.get(word) + 1);
        }
        return true;
    }

}

因为子串要与 words 中的单词完全匹配，所以字串的长度是固定的，即words中所有单词的长度之和，那么我们可以考虑是用滑块的形式，如图：

s是字符串，方框部分就是我们所说的滑块，他的长度是固定的，我们通过i的递增即可实现滑块从左滑到右，保证能遍历出s的所有子串sub。那么接下来的问题就是如何判断sub和我们的words中的所有单词是否匹配，即代码中的matching方法。

我们这里使用的是词频对比的方法，恰好题目规定，words中的所有单词长度是一样的，所以针对子串sub，我们可以按照长度进行拆分成一连串的单词，之后遍历这些单词，和要求的词频map（这里的map指的是words数组中的词频，可以提前计算得出）进行比较。因为子串的长度和单词的长度都是固定的，所以想要子串和words能匹配上，则子串拆分出来的单词词频subMap和words的词频wordsMap应该是完全一致的。由此即可实现匹配方法。