# Ac solution code

• The basic idea is using a map to count the amount of each distinct word, and then validate whether the substring starting with i is a concatenation of each word in words.

Runtime complexity = O(n^2 + wordsSize ) in the Worst Case

``````O(wordsSize): Count the amount for each distinct word
O(n^2): Validate substrings

1) In the Worst Case: all substrings appear in words list, e.g. "aaaaaaaaaaaaaaaaaa...", {"a", "a", "a", "a", "a", "a"... }.
2) On average, it will be much faster than O(n^2 + wordsSize ), because once substring doesn't match words list, loop will break.
``````

JAVA Code:

``````public List<Integer> findSubstring(String s, String[] words) {
Map<String, Integer>map = new HashMap<String, Integer>();
//Runtime = O(wordsSize)
for (String w : words) map.put(w, map.containsKey(w) ? map.get(w) + 1: 1);// Count the amount for each distinct word

int len = words[0].length(), allLen = len * words.length;
for (int i = 0; i <= s.length() - allLen; i++) {//Runtime = O(n) * O(validate function) = O(n) * O(n) = O(n^2)
Map<String, Integer>mapTmp = new HashMap<String, Integer>(map);
if (validate(s, i, len, allLen, mapTmp))// Validate whether the substring starting with i is a concatenation of each word in words
}
return res;
}

//Runtime = O(n/wordLength * wordLength) = O(n)
private boolean validate(String s, int i, int len, int allLen, Map<String, Integer>map) {
for (int j = i; j < i + allLen; j+=len) {//Runtime = O(n/wordLength)
String str = s.substring(j, j + len);// Runtime = O(wordLength)
if (map.get(str) == null) return false;
int count = map.get(str);
if (count == 1) map.remove(str);
else map.put(str, count - 1);

if (map.isEmpty())// All words are placed concatenately
return true;
}
return false;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.