lc30 Substring with Concatenation of All Words

两个hashmap

一个用来记录words[]中每种单词的出现次数，用来之后做匹配

一个用来记录source字符串i~j中每种单词出现次数，与前者比对

思路就是检查source字符串所有连续的长为words[].length()*words[0].length的子串

for(i=0; i<s.length() - words.length()*words[0].length; i++)

 

1 class Solution { 2     public List
     
       findSubstring(String s, String[] words) { 3         if(s.length() == 0 || words.length == 0) 4             return new ArrayList
      
       (); 5         HashMap
       
         count = new HashMap<>(); 6          7         for(String i : words) 8             count.put(i, count.getOrDefault(i, 0) + 1); 9         int len = words[0].length();10         int wordsNum = words.length;11         List
        
          res = new ArrayList<>();12         13         for(int i=0; i
         
           seenWords =  new HashMap<>();15             int j = 0;16             while(j < wordsNum){17                 String word = s.substring(i + j*len, i + (j+1)*len);18                 if(count.containsKey(word)){19                     seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);20                     if(seenWords.get(word) > count.get(word))21                          break;22                 23                 }else24                     break;25                 j++;26             }27             if(j == wordsNum){28                 res.add(i);29             }30         }31         return res;32     }33 }