30. Substring with Concatenation of All Words

Method 1: Brute Force.java

class Solution {
    public List<Integer> findSubstring(String str, String[] words) {
        Map<String, Integer> wordFrequencyMap = new HashMap<>();
        for (String word : words)
            wordFrequencyMap.put(word, wordFrequencyMap.getOrDefault(word, 0) + 1);

        List<Integer> res = new ArrayList<Integer>();
        int wordsCount = words.length;
        int wordLength = words[0].length();

        /// Start with each position
        for (int start = 0; start <= str.length() - wordsCount * wordLength; start++) {
            Map<String, Integer> wordsSeen = new HashMap<>();
            
            /// Check each word starting at 'start'
            for (int j = 0; j < wordsCount; j++) {
                int nextWordIndex = start + (j * wordLength);
                // get the next word from the string
                String word = str.substring(nextWordIndex, nextWordIndex + wordLength);
                
                if (!wordFrequencyMap.containsKey(word)) // break if we don't need this word
                    break;

                wordsSeen.put(word, wordsSeen.getOrDefault(word, 0) + 1); // add the word to the 'wordsSeen' map

                // no need to process further if the word has higher frequency than required 
                if (wordsSeen.get(word) > wordFrequencyMap.getOrDefault(word, 0))
                    break;

                if (j + 1 == wordsCount) // store index if we have found all the words
                    res.add(start);
            }
        }

        return res;
    }
}

Method 2: Sliding Window (V2).java

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // cuz words in words are same length, we cut s into substrings with "len" length; 
        // this problem converted to LC438. 
        
        List<Integer> res = new ArrayList<>();
        if(words == null || words.length == 0) return res;
        
        int distinctWordCount = 0;
        Map<String, Integer> wordDict = new HashMap<>();
        for(String word : words) {
            wordDict.put(word, wordDict.getOrDefault(word, 0) + 1);
            if(wordDict.get(word) == 1) distinctWordCount++;
        }
        
        int wordLen = words[0].length();
        
        for(int k = 0; k < wordLen; k++) {
            Map<String, Integer> map = new HashMap<>();

            int start = k, matched = 0;
            
            for(int end = k; end <= s.length() - wordLen; end += wordLen) { // word by word

                if((end - start) / wordLen == words.length) {
                    String rmvWord = s.substring(start, start + wordLen);
                    if(wordDict.containsKey(rmvWord)) {
                        map.put(rmvWord, map.get(rmvWord) - 1);
                        if(map.get(rmvWord).equals(wordDict.get(rmvWord) - 1)) matched--;
                    }
                    start += wordLen;
                }
                
                String addWord = s.substring(end, end + wordLen);
                if(wordDict.containsKey(addWord)) {
                    map.put(addWord, map.getOrDefault(addWord, 0) + 1);
                    if(map.get(addWord).equals(wordDict.get(addWord))) matched++;
                }
                
                if(matched == distinctWordCount) res.add(start);
            }
        }
  
        return res;
    }
}

Method 2: Sliding Window.java

public class Solution {
    public List<Integer> findSubstring(String str, String[] words) {
        List<Integer> res = new LinkedList<>();
        
        if (words.length == 0 || str.length() < words.length * words[0].length())
            return res;
        
        int n = str.length(), k = words[0].length();
        int winSize = words.length * k;

        Map<String, Integer> wordCountMap = new HashMap<>(), curMap = new HashMap<>();
        for (String w : words) {
            wordCountMap.put(w, wordCountMap.getOrDefault(w, 0) + 1);
        }
        int matchCount = 0;
        
        for (int i = 0; i < k; i++) {
            
            int start = i, end = i;
            
            /// Try each possible start position
            while (end + k <= n) {
                
                String endWord = str.substring(end, end + k);
                
                /// [Grow] Update the window state
                if (wordCountMap.containsKey(endWord)) {
                    curMap.put(endWord, curMap.getOrDefault(endWord, 0) + 1);
                    if(curMap.get(endWord).equals(wordCountMap.get(endWord))) {
                        matchCount++;
                    }
                }
                
                end += k;

                if(end - start == winSize) {
                    /// [Update Result] Check if found a full match 
                    if (matchCount == wordCountMap.size()) {
                        res.add(start);
                    }
                    
                    /// [Shrink] Update the window state
                    String startWord = str.substring(start, start + k);
                    
                    if (wordCountMap.containsKey(startWord)) {
                        curMap.put(startWord, curMap.getOrDefault(startWord, 0) - 1);
                        if(curMap.get(startWord).equals(wordCountMap.get(startWord) - 1)) {
                            matchCount--;
                        }
                    }
                    
                    start += k;
                }
            }
            
            curMap.clear();
            matchCount = 0;
        }
        return res;
    }
}

• 由於欲尋找的詞組 words 都是等長的字串，故首先以該長度將欲搜尋的字串 s 去分割成好幾個詞組。例如：欲搜尋的字串 s 為 "barfoothefoobarman" ，而欲搜尋的詞組 words 為 ["foo","bar"] ，則以長度為 3 去切割字串，分別從開頭的索引值是 0, 1, 2 切成三次去尋覽，分割的結果分別是 "bar|foo|the|foo|bar|man" 、 "(b)arf|oot|hef|oob|arm(an)" 和 "(ba)rfo|oth|efo|oba|rma(n)"。

• 接著對於每一個分割的結果利用 Sliding Window 的方式去尋找是否能夠滿足整個欲搜尋的詞組 words ，當 Window 滑動到下個分割出來的詞組時，若符合則記住符合欲搜尋的詞組 words 中的第幾個；若無法符合則先去除最前面搜尋到的詞組再試一次，這樣的過程中遇到已經完美組合的狀況則記住答案，一直到全部分割的詞組都找過為止。

• https://knightzone.studio/2019/03/29/4127/leetcode%EF%BC%9A30-substring-with-concatenation-of-all-words/