6/20/2014

136. Substring with Concatenation of All Words

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        HashMap<String, Integer> toFind = new HashMap<String, Integer> ();
        HashMap<String, Integer> found = new HashMap<String, Integer> ();
       
        int m = L.length;
        int n = L[0].length();
       
        for (int i=0; i<m; i++) {
            if (!toFind.containsKey(L[i])) {
                toFind.put(L[i], 1);
            } else {
                toFind.put(L[i], toFind.get(L[i])+1);
            }
        }
       
        for (int i=0; i<=S.length()-m*n; i++) {
            found.clear();
            int j;
            for (j=0; j<m; j++) {
                int k = i+j*n;
                String substr = S.substring(k, k+n);
                if (!toFind.containsKey(substr)) break;
                if (!found.containsKey(substr)) {
                    found.put(substr, 1);
                } else {
                    found.put(substr, found.get(substr)+1);
                }
                if (found.get(substr)>toFind.get(substr)) break;
            }
            if (j==m) res.add(i);
        }
       
        return res;
    }
}

没有评论:

发表评论