30. 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 words exactly 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).

Solution:

Using HashMap + two pointers.

• Using hashMap hm to count all the words in words and its appearance times
• traverse through the string, with two loops:
  • loop1 traverse from i = 0 to i = 0 + word_length - 1
  • loop2 traverse from i to the string end with step of word length
• Using another hashMap curr to keep track the appearance of word appear in both string s and word dictionary
  • if the current word in string is also in our words dictionary, update its appearance times
    • if the appearance times in current hashmap is lower than the word dictionary
      • total_cnt++
    • else ----> this word appeared more times than expected, need to move the left pointer until the current word appearance time is below the maximum in word dictionary
      • meanwhile, update the curr hashmap of previous which get removed form the current substring
      • update the cnt
    • if the totalcnt == the words length
      • update result
      • update curr hash map
      • move left pointer to the next word
      • update cnt
  • else if the current word not in the hashmap, all the previous substring cannot be part of the result,
    • clear the curr hashmap
    • cnt = 0
    • move left pointer to the next word

public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        Map<String,Integer> hm = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            if(!hm.containsKey(words[i])){
                hm.put(words[i], 1);
            }else{
                hm.put(words[i],hm.get(words[i]) + 1);
            }
        }

        int word_len = words[0].length();

        for(int i = 0; i < word_len; i++){
            Map<String, Integer> currmap = new HashMap<>();
            int cnt = 0;
            int left = i;

            for(int j = i; j <= s.length() - word_len; j+=word_len){
                String word = s.substring(j, j+word_len);

                if(hm.containsKey(word)){
                    if(currmap.containsKey(word)){
                        currmap.put(word, currmap.get(word) + 1);
                    }else{
                        currmap.put(word, 1);
                    }

                    if(hm.get(word) >= currmap.get(word)){
                        cnt++;
                    }else{
                        while(currmap.get(word) > hm.get(word)){
                            String tmp = s.substring(left, left+word_len);
                            if(currmap.containsKey(tmp)){
                                currmap.put(tmp, currmap.get(tmp) - 1);
                                if(currmap.get(tmp) < hm.get(tmp)){
                                    cnt--;
                                }
                                //cnt--;
                            }
                        left += word_len;
                        }
                    }

                    if(cnt == words.length){
                        res.add(left);
                        String tmp = s.substring(left,left+word_len);
                        currmap.put(tmp, currmap.get(tmp) - 1);
                        cnt--;
                        left += word_len;
                    }
                }else{//not contain this word in hm
                    currmap.clear();
                    cnt = 0;
                    left = j + word_len;
                }
            }
        }
         return res;

    }

Reference:

http://blog.csdn.net/linhuanmars/article/details/20343903