首页 > 代码库 > 【LeetCode】Substring with Concatenation of All Words

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

public class Solution {
       public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int wordLen = L[0].length();
        int numOfWords = L.length;
        int length = wordLen * numOfWords; // substring length
        if (S.length() < length)
            return list;

        // initialize a hash map to facilitate the word match by word counting
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (String word : L) {
            if (!map.containsKey(word)) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }

        for (int i = 0; i <= S.length() - length; i++) {
            String substr = S.substring(i, i + length);
            HashMap<String, Integer> map2 = (HashMap<String, Integer>) map
                    .clone();
            // partition the substring into the words of equal length
            while (true) {
                String word = substr.substring(0, wordLen);
                if (map2.containsKey(word)) {
                    int num = map2.get(word) - 1;
                    // not found: too many occurrences
                    if (num < 0) {
                        break;
                    }
                    map2.put(word, num);
                    substr = substr.substring(wordLen);
                    // found
                    if (substr.isEmpty()) {
                        list.add(i);
                        break;
                    }
                }
                // not found: unmatched
                else {
                    break;
                }
            }
        }

        return list;
    }
}