leetcode 30. Substring with Concatenation of All Words 这个构造巧妙 值得一刷。
终于ACC! 开心！
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Solution { public static void main(String[] args){ String s = "aaaaaaaa"; Solution k = new Solution(); String[] words = {"aa","aa","aa"}; 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> ans = new ArrayList<Integer>(); Map<String,Integer> wordsSet = new HashMap<String,Integer>(); Map<String,Integer> twords = new HashMap<String,Integer>(); int slen = s.length(); int n = words.length; int wlen = words[0].length(); int index = 0; for(String word :words){ if(wordsSet.containsKey(word)){ int val = wordsSet.get(word); wordsSet.put(word, val+1); }else{ wordsSet.put(word, 1); twords.put(word, index++); } } int[] flag = new int[index]; for(int i=0;i<wlen;i++){ int left = i; int count = 0; flag = new int[index]; for(int j=i;j+wlen<=slen;j=j+wlen){ String cur = s.substring(j,j+wlen); if(wordsSet.containsKey(cur)){ int fn = flag[twords.get(cur)]; if(fn<wordsSet.get(cur)){ count++; fn++; flag[twords.get(cur)] = fn; if(count==n){ //find ans.add(left); String word = s.substring(left,left+wlen); flag[twords.get(word)] -= 1; count--; left = left + wlen; } }else{ // more flag[twords.get(cur)] = ++fn; // +1 while(flag[twords.get(cur)]>wordsSet.get(cur)){ String word = s.substring(left,left+wlen); if(flag[twords.get(word)]<=wordsSet.get(word)) count--; flag[twords.get(word)] -= 1; left = left + wlen; } } }else{ flag = new int[index]; count = 0; left = j+wlen; } } } return ans; } }
