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应该是完全一致的。由此即可实现匹配方法。