题目: 串联所有单词的子串

分析

因为匹配单词 words 的长度相同，可以通过 words 数组长度和任意一个 word 的长度计算出来串联之后子串的长度，比如为 length 。

可以穷举 s 所有的长度为 length 的字符串子串，判断这些子串是否包含 words 所有的单词。

穷举法

计算串联子串的长度，使用 words 中的第一个单词的长度乘以 words 数组的长度，得出 length。

将 words 的单词存入 Hash 表，因为 words 中可能有重复单词，所以 Hash 表中的 Key 可以设计为单词的值， Value 设计为这个单词出现的次数。

循环所有的 s 长度为 length 的子串，从位置 0 开始循环，直到位置为 s.length() - length。

通过之前存储的 Hash 表比较这些子串是否包含 words 中所有的单词，将子串切割为 word 单词长度的单词，去Hash表中查询是否存在这个单词。

如果 Hash 表不存在该单词，则表明不匹配，可以进行下一个子串的匹配。

如果存在而且 Value 为 0 ，则将 Hash 表这个单词删除，如果存在且 Value 大于 0 ，则将 Value 的值进行减一操作，

当该子串所有的单词都可以匹配 Hash 表中的单词，则表明该子串是符合题意的解。

题解

穷举法

class Solution {
    public List<Integer> solute(String s, String[] words) {
        if(s.length() == 0 || words.length == 0) return result;
        
        Map<String, Integer> wordsCounter = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        int length = words[0].length();
        
        // 存储所有的单词到 Hash 表
        for(String word : words){ 
            if(wordsCounter.containsKey(word)) 
                wordsCounter.put(word, wordsCount.get(word)+1);
            else 
                wordsCounter.put(word, 1);
        }
        
        for(int i = 0; i < length; ++i){ 
            Map<String, Integer> window = new HashMap<>();
            int left = i;
            int right = i;
            while(right <= s.length()-length && left <= s.length()-length*words.length){
                String patternWord = s.substring(right, right + length);
                
                if(!wordsCounter.containsKey(patternWord)){
                    window.clear();
                    right += length;
                    left = right;
                    continue;
                }
                
                if(window.containsKey(patternWord)) 
                    window.put(patternWord, window.get(patternWord)+1);
                else 
                    window.put(patternWord, 1);
                
                while(window.get(patternWord) > wordsCounter.get(patternWord)){
                    String subLeft = s.substring(left, left + length);
                    if(window.get(subLeft) == 1) 
                        window.remove(subLeft);
                    else 
                        window.put(subLeft, window.get(subLeft)-1);
                    left += length;
                }
                right += length;
                
                if(right-left == length*words.length) 
                    result.add(left);
            }
        }
        return result;
    }
}