Leetcode–Substring with Concatenation of All Words

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:

1. Use a hash map to store word and its occurrence.
2. Two pointers: start and end, to record from each start if can reach an end that covers all words in L.
3. Attention to the for loop conditions, optimize the ending condition to cut the unnecessary iterations.
4. 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.

1. 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)
2. Start and end pointer forms a sliding window:
   1. 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.
   2. 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.
3. 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