Lexi's Leetcode solutions

[leetcode] Substring with Concatenation of All Words | foobar题

Posted on: November 10, 2013

给一个String[] L,里面可以有重复,在S里找能包括所有L且都只出现一次的window的start。比如foobarthebarfooman, L={foo, bar}, return 0, 9.
这题正经做了一段时间。

public ArrayList<Integer> findSubstring(String S, String[] L) {
    final Map<String, Integer> need = new HashMap<String, Integer>();
    for (int i = 0; i < L.length; i++) {
        need.put(L[i], need.get(L[i]) == null ? 1 : need.get(L[i]) + 1);
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < L[0].length(); i++) {
        populateResult(result, S, L, i, need);
    }
    return result;
}
private void populateResult(ArrayList<Integer> result, String S, String[] L, 
                            int start, final Map<String, Integer> need) {
    int k = L[0].length();
    HashMap<String, Integer> has = new HashMap<String, Integer>();
    for (int end = start; end <= S.length() - k; end += k) {
        String sub = S.substring(end, end + k);
        if (need.containsKey(sub)) {
            while (has.get(sub) == need.get(sub)) {
                String tmp = S.substring(start, start + k);
                has.put(tmp, has.get(tmp) - 1);
                start += k;
            }
            has.put(sub, has.get(sub) == null ? 1 : has.get(sub) + 1);
            if (end - start + k == L.length * L[0].length())
                result.add(start);
        } else {
            has.clear();
            start = end + k;
        }
    }
}
Tags: ,

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: