leetcode 30. Substring with Concatenation of All Words
又一个TLE ：
import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; public class Solution { public static void main(String[] args){ String s = "barfoofoobarthefoobarman"; Solution k = new Solution(); String[] words = {"foo","bar","the"}; List<Integer> ans = k.findSubstring(s,words); for(int a :ans){ System.out.println(a); } } public List<Integer> findSubstring(String s, String[] words) { List<Integer> pos = new ArrayList<Integer>(); List<Integer> ans = new ArrayList<Integer>(); Map<String,Integer> wordsSet = new HashMap<String,Integer>(); int slen = s.length(); int i = 0; for(String word :words){ if(wordsSet.containsKey(word)){ int val = wordsSet.get(word); wordsSet.put(word, val+1); }else{ wordsSet.put(word, 1); } } Map<String,Integer> copy = new HashMap<String,Integer>(wordsSet); int wlen = words[0].length(); while(i+wlen<=slen){ String part = s.substring(i,i+wlen); if(wordsSet.containsKey(part)){ pos.add(i); } i++; } int k =0; int j = 0; while(k<pos.size()){ j = pos.get(k); boolean isfind = false; boolean isfailure = false; while(!isfailure&&!isfind&&j+wlen<=slen){ String curWord = s.substring(j,j+wlen); int cnt = 0; if(wordsSet.containsKey(curWord)){ cnt = wordsSet.get(curWord); } if(pos.contains(j)&&wordsSet.containsKey(curWord)){ wordsSet.put(curWord, --cnt); if(cnt==0){ wordsSet.remove(curWord); } if(wordsSet.size()==0){ isfind = true; ans.add(pos.get(k)); }else{ j = j+ wlen; } }else{ isfailure = true; } } wordsSet = new HashMap<String,Integer>(copy); k++; } return ans; } }