[LeetCode]30. Concatenate substrings of all words

subject

30.  Concatenate the substrings of all words 
 Given a string  s  And some of the   Same length   's words  words . find  s  It happens that  words  The starting position of the substring formed by concatenation of all words in .

 Pay attention to the relationship between the string and  words  The words in match exactly , No other characters in the middle  , But there's no need to think about  words  The order in which words are concatenated .

 

 Example  1：

 Input ：s = "barfoothefoobarman", words = ["foo","bar"]
 Output ：[0,9]
 explain ：
 From the index  0  and  9  The first substrings are  "barfoo"  and  "foobar" .
 The order of output is not important , [9,0]  It's also a valid answer .
 Example  2：

 Input ：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 Output ：[]
 Example  3：

 Input ：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 Output ：[6,9,12]
 

 Tips ：

1 <= s.length <= 104
s  It's made up of lowercase letters 
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]  It's made up of lowercase letters 

Method 1： Hash + Compare

        public List<Integer> findSubstring(String s, String[] words) {
    
            Map<String, Integer> dict = new HashMap<>();//words Dictionary map,k Is the current word word v Is the number of occurrences 
            int len = 0, w_len = 0; // The total length , When the length of a word , The length of each word is equal , Just record one 
            for (String word : words) {
    
                len += word.length();
                w_len = word.length();
                dict.put(word, dict.getOrDefault(word, 0) + 1);
            }
            int n = s.length();
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i + len - 1 < n; i++) {
    
                Map<String, Integer> can = new HashMap<>();// Candidate map
                String sub = s.substring(i, i + len);
                // System.out.println(sub);
                // Every time w_len Segmentation of words in steps of 
                for (int j = 0; j < len; j += w_len) {
    
                    String seg = sub.substring(j, j + w_len);
                    can.put(seg, can.getOrDefault(seg, 0) + 1);
                }
                //dict And can In unison , Description can form 
                if (dict.equals(can)) {
    
                    res.add(i);
                }
            }
            return res;
        }