首页 > 代码库 > Leetcode-Substring with Concatenation of All Words
Leetcode-Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
Analysis:
For a chain starting at position i, we will chase it to the end of S and put every word on this chain into a list one by one. We record the number of a word appears in array L and store them as dict. If a word is not in the dict, then the whole word list is cleared. If a word is in the dict but the number of this word appeared in the list has already be the maximum, we then remove the head of the word list until we remove this word once. If after adding some word into the list, the number of words in the list equals to the length of the array L, we then find a starting postion. In addition, we need to check such chain starting at 0..wordLen-1.
Solution:
1 public class Solution { 2 public List<Integer> findSubstring(String S, String[] L) { 3 List<Integer> res = new ArrayList<Integer>(); 4 if (S.isEmpty() || L.length==0 || S.length()<L[0].length()) return res; 5 6 for (int i=0;i<L[0].length();i++) 7 findSubstringSub(S,L,i,res); 8 9 return res;10 }11 12 public void findSubstringSub(String S, String[] L, int start, List<Integer> res){13 Map<String,Integer> wordSet = new HashMap<String,Integer>();14 List<String> wordList = new LinkedList<String>(); 15 for (int i=0;i<L.length;i++)16 if (wordSet.containsKey(L[i]))17 wordSet.put(L[i],wordSet.get(L[i])+1);18 else wordSet.put(L[i],1);19 20 int index = start;21 int wordLen = L[0].length();22 while (index+wordLen-1<S.length()){23 String word = S.substring(index,index+wordLen);24 if (!wordSet.containsKey(word)){25 while(wordList.size()>0){26 String temp = wordList.get(0);27 wordList.remove(0); 28 wordSet.put(temp,wordSet.get(temp)+1);29 }30 index += wordLen;31 } else {32 int left = wordSet.get(word);33 wordSet.put(word,left-1);34 wordList.add(word); 35 index+=wordLen;36 37 if (left-1<0){38 while (!wordList.get(0).equals(word)){39 String temp = wordList.get(0);40 wordList.remove(0); 41 wordSet.put(temp,wordSet.get(temp)+1);42 }43 String temp = wordList.get(0);44 wordList.remove(0); 45 wordSet.put(temp,wordSet.get(temp)+1);46 }47 int size = wordList.size();48 if (size==L.length)49 res.add(index-L.length*L[0].length());50 51 52 }53 }54 55 return;56 57 } 58 59 }
Leetcode-Substring with Concatenation of All Words