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

### 代码​

// Substring with Concatenation of All Words// 时间复杂度O(n*m)，空间复杂度O(m)public class Solution {    public List<Integer> findSubstring(String s, String[] words) {        final int wordLength = words[0].length();        final int catLength = wordLength * words.length;        List<Integer> result = new ArrayList<>();        if (s.length() < catLength) return result;        HashMap<String, Integer> wordCount = new HashMap<>();        for (String word : words)            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);        for (int i = 0; i <= s.length() - catLength; ++i) {            HashMap<String, Integer> unused = new HashMap<>(wordCount);            for (int j = i; j < i + catLength; j += wordLength) {                final String key = s.substring(j, j + wordLength);                final int pos = unused.getOrDefault(key, -1);                if (pos == -1 || pos == 0) break;                unused.put(key, pos - 1);                if (pos - 1 == 0) unused.remove(key);            }            if (unused.size() == 0) result.add(i);        }        return result;    }}