Substring with Concatenation of All Words, Leetcode 解题笔记

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).

这道题的思路比较特殊,没什么可移植性,很直接,这里为了省时间copy了网上的解释和代码,很容易理解:

Analysis:

Try to think this problem straightforward:
Say in L there are m strings with length n.
What string is required to match in S? A length of m*n string start with each position in S.
What is a match? In the m*n long string, every string in L appear only once.

So the algorithm is:
Scan every m*n long string start from each position in S, see if all the strings in L have been appeared only once using Map data structure. If so, store the starting position.

Yes, do not consider any DP or DFS solutions, just using the hash map and loop.

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(L==null || L.length==0) return null; 
        int n = L.length, m = L[0].length(), l=S.length();
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        Map<String,Integer> covered = new HashMap<String,Integer>();
        for(int j=0;j<n;j++){
            if(covered.containsKey(L[j])){
                covered.put(L[j],covered.get(L[j])+1);
            }else{
                covered.put(L[j], 1);
            }
        }
        
        int i=0;
        while(l-i>=n*m){
            Map<String, Integer> temp = new HashMap<String, Integer>(covered);
            for(int j=0;j<n;j++){
                String testStr = S.substring(i+j*m,i+(j+1)*m);
                if(temp.containsKey(testStr)){
                    if(temp.get(testStr)-1==0)
                        temp.remove(testStr);
                    else
                        temp.put(testStr,temp.get(testStr)-1);
                }else
                    break;
            }
            if(temp.size()==0) res.add(i);
            i++;
        }
        return res;    
    }
}
Advertisements

One thought on “Substring with Concatenation of All Words, Leetcode 解题笔记

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