題目描述：給定一個字符串?s?和一些長度相同的單詞?words。找出 s 中恰好可以由?words 中所有單詞串聯(lián)形成的子串的起始位置。
注意子串要與?words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮?words?中單詞串聯(lián)的順序。
示例：輸入：
? s = "barfoothefoobarman",
? words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoor" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案。
java代碼：
class Solution {
? ? public List<Integer> findSubstring(String s, String[] words) {
? ? ? ? List<Integer> res = new ArrayList<Integer>();
? ? ? ? int wordNum = words.length;
? ? ? ? if(wordNum == 0) return res;
? ? ? ? int wordLen = words[0].length();
? ? ? ? //HashMap1存所有單詞
? ? ? ? HashMap<String,Integer> allWords = new HashMap<String,Integer>();
? ? ? ? for(String w:words) {
? ? ? ? ? ? int value = allWords.getOrDefault(w,0);
? ? ? ? ? ? allWords.put(w,value+1);
? ? ? ? }
? ? ? ? //遍歷所有子串
? ? ? ? for(int i=0;i<s.length()-wordNum*wordLen+1;i++) {
? ? ? ? ? ? //HshMap2存當(dāng)前掃描的字符串含有的單詞
? ? ? ? ? ? HashMap<String,Integer> hasWords = new HashMap<String,Integer>();
? ? ? ? ? ? int num = 0;
? ? ? ? ? ? while(num < wordNum) {
? ? ? ? ? ? ? ? String word = s.substring(i + num*wordLen,i+(num+1)*wordLen);
? ? ? ? ? ? ? ? //判斷該單詞是否在HashMap1中
? ? ? ? ? ? ? ? if(allWords.containsKey(word)) {
? ? ? ? ? ? ? ? ? ? int value = hasWords.getOrDefault(word,0);
? ? ? ? ? ? ? ? ? ? hasWords.put(word,value+1);
? ? ? ? ? ? ? ? ? ? //判斷當(dāng)前單詞的value和HashMap1中該單詞的value
? ? ? ? ? ? ? ? ? ? if(hasWords.get(word) > allWords.get(word)) {
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? num++;
? ? ? ? ? ? }
? ? ? ? ? ? if(num == wordNum) {
? ? ? ? ? ? ? ? res.add(i);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}
