The Problem:
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).
Notes:
- Use a hash map to store word and its occurrence.
- Two pointers: start and end, to record from each start if can reach an end that covers all words in L.
- Attention to the for loop conditions, optimize the ending condition to cut the unnecessary iterations.
- Mistake I made: each time change a new start, map and got need to be reinitialized.
Java Solution:
public class Solution { public List<Integer> findSubstring(String S, String[] L) { List<Integer> ind = new ArrayList<Integer>(); if(L.length==0)return ind; int len = L[0].length(); HashMap<String, Integer> map = new HashMap<String, Integer>(); for(int i = 0; i < L.length; i++){ if(map.containsKey(L[i])){ int t = map.get(L[i]); map.put(L[i], t+1); } else{ map.put(L[i], 1); } } for(int start = 0; start <= S.length()-L.length *len; start++){ //--!! iteration can stop when not enough word from start to cover all in L HashMap<String, Integer> tmpmap = new HashMap<String, Integer>(map); int got = 0; //--!! each new start needs to reset got for(int i = start; i <= start + (L.length-1) * len; i=i+len){ //--!!check the bundary before call substring if(i+len > S.length()) break; String sub = S.substring(i, i+len); if(tmpmap.containsKey(sub)){ got++; int c = tmpmap.get(sub); if(c>1) tmpmap.put(sub, c-1); else tmpmap.remove(sub); } else{ break; } } if(got == L.length){ ind.add(start); } } return ind; } }
Java Solution II :
I came up with another solution, which reduced execution time a lot, but code is not that straightforward and concise.
- Traverse the string by chunks of word length in L (len), two pointers (start and end) always advance by len. In the out-most loop, iterate all possibility of starting point in S, (0,1,…len-1)
- Start and end pointer forms a sliding window:
- Each time find a match, end pointer advance. If the number of match reaches L.length, add back the start word to map, decrease number of match, then move start to next, and in next iteration see if end can form another valid window.
- Each time find a mismatch, while start < end, add back the start word to map, move start forward to next word, and decrease the number of match, decrease end to check for the same word again in next iteration. Because there are cases that end exists in the original map, but previous traversed end has the same value and already removed that word from map.
- Again each time start move to next, check if the remaining characters from start enough for all the words in L.
public class Solution { public List<Integer> findSubstring(String S, String[] L) { if(S.length()==0 || L.length==0)return null; // create a hash table for L HashMap<String, Integer> Lmap = new HashMap<String, Integer>(); for(String str : L){ if(Lmap.containsKey(str)){ int c = Lmap.get(str); Lmap.put(str,c+1); } else Lmap.put(str, 1); } List<Integer> result = new ArrayList<Integer>(); int start = 0; int len = L[0].length(); int match = 0; HashMap<String, Integer> map = new HashMap<String, Integer>(Lmap); for(int j = 0; j < len; j++){ start = j; for(int i = j; i+len <= S.length(); i+=len){ String sub = S.substring(i, i+len); if(map.containsKey(sub)){ match++; int c = map.get(sub); if(c>1) map.put(sub, c-1); else map.remove(sub); if(match==L.length){ result.add(start); // start advance for one word, if that word found in next i, then found another complete match match--; if((start+len * L.length) <= S.length()){ map.put(S.substring(start, start+len), 1); start = start+len; } else break; } } else{ // mismatch, reset start, map and match match--; if((start+len * L.length)<= S.length()){ if(start<i){ map.put(S.substring(start, start+len), 1); start = start+len; i-=len; } else{ map = new HashMap<String, Integer>(Lmap); match = 0; start+=len; } } else break; } } match=0; // !!!---remember to reset match, and set back the start map = new HashMap<String, Integer>(Lmap); } return result; } }
Advertisements