2014年4月11日 星期五

[LeetCode] Substring with Concatenation of All Words

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).
Solution:O(n)
public class Solution {
      public ArrayList<Integer> findSubstring(String S, String[] L){
        if(L==null || L.length==0) 
            return null; 
        
        int n = L.length;
        int m = L[0].length();
        int l = S.length();
        ArrayList<Integer> ret = new ArrayList<Integer>();
        
        Map<String,Integer> cmap = new HashMap<>();
        for(int j=0;j<n;j++){
            if(cmap.containsKey(L[j])){
                cmap.put(L[j],cmap.get(L[j])+1);
            }else{
                cmap.put(L[j], 1);
            }
        }
        
        int i=0;
        while(l-i>=n*m){
            Map<String, Integer> map = new HashMap<>(cmap);
            for(int j=0;j<n;j++){
                String str = S.substring(i+j*m,i+(j+1)*m);
                if(map.containsKey(str)){
                    if(map.get(str)-1==0)
                        map.remove(str);
                    else
                        map.put(str,map.get(str)-1);
                }else
                    break;
            }
            if(map.size()==0) ret.add(i);
            i++;
        }
        return ret;    
    }
}

沒有留言:

張貼留言