LeetCode 30. 与所有单词相关联的字串 Substring with Concatenation of All Words

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

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

示例 1:

输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出:

[0,9]

解释: 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:
  s = "wordgoodstudentgoodword",
  words = ["word","student"]
输出:

[]

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> ret=new ArrayList<Integer>();  
        if ( s==null || words==null || words.length==0 ) {
            return ret;  
        } 
        HashMap<String,Integer> maps=new HashMap<String,Integer>();  
        for(int i=0;i<words.length;i++){  
            if ( maps.containsKey(words[i]) ){  
                int t = maps.get(words[i]);  
                maps.put(words[i], t+1);  
            }else{  
                maps.put(words[i],1);  
            }  
              
        }  
          
        int wordLength=words[0].length();  
        for(int i=0;i<wordLength;i++){  
            HashMap<String,Integer> need =new HashMap<String,Integer>(maps);  
            int start=i,end=i;  
            int needCnt=words.length;  
            if ( (s.length()-start)< (wordLength*needCnt)) {
                break;  
            } 
                  
            for(;end<s.length();end+=wordLength){  
                if ( s.length()-end < wordLength ) {
                    break;  
                } 
                String tmp= s.substring(end,end+wordLength);  
                if (maps.containsKey(tmp)){  
                    int t=need.get(tmp);  
                    need.put(tmp,t-1);  
                    if ( t>0)  {
                        needCnt--;  
                    }
                }  
                  
                if ( needCnt==0 ){  
                    while(true){  
                        String toRemove=s.substring(start,start+wordLength);  
                        if (maps.containsKey(toRemove) ){  
                            int t =need.get(toRemove);  
                            if ( t <0 ){  
                                need.put(toRemove,t+1);  
                            }  
                            else  
                                break;  
                        }  
                        start+=wordLength;  
                    }  
                    if (end-start == wordLength*(words.length-1)) {
                        ret.add(start);  
                    } 
                }  
            }  
        }  
        return ret;  
    }  
}