[leetcode] Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

 

Correct Ans:

public class Solution {
 public List<Integer> findSubstring(String s, String[] words) {
 List<Integer> res = new ArrayList<Integer>();
 
 if(s==null||words==null||words.length*words[0].length()>s.length()) return res;
 
 int wordLen = words[0].length();
 int len = words.length;
 
 Map<String, Integer> dict = new HashMap<String, Integer>();
 
 for(String word: words)
 if(dict.containsKey(word)) dict.put(word,dict.get(word)+1);
 else dict.put(word,1);
 
 for(int j=0; j<wordLen; j++){ //if the first several char is not is the dict, eg. bkapp vs [app]
 Map<String, Integer> leftover = new HashMap<String,Integer>(dict);
 Queue<String> queue = new LinkedList<String>();
 
 for(int i=j; i<=s.length()-wordLen; i+=wordLen){
 String cur = s.substring(i,i+wordLen);
 if(dict.containsKey(cur)){
 queue.add(cur);
 if(leftover.get(cur)==0){
 
 while(!cur.equals(queue.element())){
 
 String oldStr = queue.remove();
 leftover.put(oldStr, leftover.get(oldStr)+1);
 }
 
 queue.remove();
 
 }else{
 leftover.put(cur, leftover.get(cur)-1);
 }
 
 if(queue.size()==len){
 res.add(i-(len-1)*wordLen);
 }
 
 }else{
 leftover=new HashMap<String,Integer>(dict);
 queue.clear();
 }
 }
 
 }
return res;
 
 }
}

 

My Ans:
1. The problem is that it cannot handle multiple identical words in dict, since we use HashSet to store dict.
2. The pros: we use map<String, Integer> to store visited word, where integer is the word’s position (start index) in S, so that when we found it again, we can quickly adjust left boarder(curPos/staring index for current examine substring).

 public List<Integer> findSubstring(String s, String[] words) {
 List<Integer> res = new ArrayList<Integer>();
 
 if(s==null||words==null||words.length*words[0].length()>s.length()) return res;
 
 int wordLen = words[0].length();
 Map<String, Integer> visited = new HashMap<String,Integer>();
 HashSet<String> dict = new HashSet<String>();
 
 for(String word: words)
 dict.add(word);
 
 int curPos = 0;
 
 for(int i=0; i<=s.length()-wordLen; i+=wordLen){
 String cur = s.substring(i,i+wordLen);
 if(dict.contains(cur)){
 if(visited.containsKey(cur)&&visited.get(cur)>=curPos){
 if(visited.size()==dict.size()){
 res.add(curPos); curPos=visited.get(cur)+wordLen; //visited.clear();
 }else{
 curPos=visited.get(cur)+wordLen; 
 }
 visited.put(cur,i);
 }else{ visited.put(cur,i); if(visited.size()==1) curPos=i;}
 }else{
 if(visited.size()==dict.size())
 res.add(curPos);
 visited.clear();
 }
 }

 return res;
 
 }

Advertisements
This entry was posted in coding. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s