[Leetcode] Substring with Concatenation of All Words

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

 

题目：给定一个字符串S，一个字符串数组L，找出S中所有这样的子串起点，该子串包含L中的所有元素。

说明：

1）L中存在重复的元素

2）子串不允许间断，即子串从开始到找全L中的所有元素之前，子串中不允许包含L以外的东西，而且，即使当前处理的子串是L中含有的，但是前面已经找够了，这个多余的也是不合法的，若此时还有L中的其他元素没找到，从这个起点开始也是不成功的。

3）L在S中出现的顺序不同考虑，任意顺序，只要全部存在就可以。

 

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> result = new ArrayList<Integer>();
        if (S.length() == 0 || L.length == 0)
            return result;
        HashMap<String, Integer> total = new HashMap<String, Integer>();
        HashMap<String, Integer> has = new HashMap<String, Integer>();
        int wordCount = L.length;
        int wordLen = L[0].length();
        int searchEnd = S.length() - wordCount * wordLen;
        if (searchEnd < 0)
            return result;
        for (String s : L) {
            if (total.containsKey(s))
                total.put(s, total.get(s) + 1);
            else
                total.put(s, 1);
        }
        for (int i = 0; i <= searchEnd; ++i) {
            has.clear();
            int j = i;
            int iWord = 0;
            for (; iWord < wordCount; ++iWord) {

                String sub = S.substring(j, j + wordLen);
                if (!total.containsKey(sub))
                    break;
                // in L, but redundancy
                if ((has.containsKey(sub))
                        && (((has.get(sub) + 1)) > total.get(sub)))
                    break;
                if (has.containsKey(sub))
                    has.put(sub, has.get(sub) + 1);
                else
                    has.put(sub, 1);
                j += wordLen;
            }
            if (iWord == wordCount)
                result.add(i);
        }
        return result;
    }
}