findSubstring

30. 串联所有单词的子串
给定一个字符串 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"]
输出：[]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if(s.length() == 0 || words.length == 0) return res;
        int wordLen = words[0].length();
        int wordNum = words.length;
        HashMap<String, Integer> validWord = new HashMap<>();
        for(String each: words){
            int v = validWord.getOrDefault(each, 0);
            validWord.put(each, v+1);
        }
        for(int j=0; j < wordLen; j++){
            int num=0;
            HashMap<String, Integer> hasWord = new HashMap<>();
            for(int i=j; i<s.length()-words.length*wordLen+1; i += wordLen){
                boolean hasRemoved = false;
                while(num < wordNum) {
                    String str = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                    if (validWord.containsKey(str)) {
                        int v = hasWord.getOrDefault(str, 0);
                        hasWord.put(str, v + 1);
                        // 匹配次数超了
                        if (hasWord.get(str) > validWord.get(str)) {
                            int removed = 0;
                            hasRemoved = true;
                            while (hasWord.get(str) > validWord.get(str)) {
                                String removeWord = s.substring(i+removed*wordLen, i+(removed+1)*wordLen);
                                int v1 = hasWord.getOrDefault(removeWord, 0);
                                hasWord.put(removeWord, v1 - 1);
                                removed++;
                            }
                            num = num - removed + 1;
                            i = i + (removed - 1) * wordLen;
                            break;
                        }
                    } else {
                        // 不匹配的情况
                        hasWord.clear();
                        i = i + num * wordLen;
                        num = 0;
                        break;
                    }
                    num++;
                }
                // 完全匹配
                if(num == wordNum){
                    res.add(i);
                }
                // 完全匹配 并且去除第一个单词
                if(num>0 && !hasRemoved){
                    String first = s.substring(i, i+wordLen);
                    int v = hasWord.getOrDefault(first, 0);
                    hasWord.put(first, v-1);
                    num--;
                }
            }
        }
        return res;
    }
}