Find All Substring Concatenations
You are given a string s and an array of strings words. All the words in words are of the same length. Your task is to find all starting indices in s of substring(s) that are a concatenation of all words in words exactly once, without any intervening characters. The order of words in the concatenation does not matter. The resulting indices should be returned in any order.
[ "barfoothefoobarman", "[\"foo\",\"bar\"]" ]
[ 0, 9 ]
Explanation. At index 0, "barfoo" is a concatenation of "bar" and "foo". At index 9, "foobar" is a concatenation of "foo" and "bar".
[ "barfoofoobarthefoobarman", "[\"bar\",\"foo\",\"the\"]" ]
[ 6, 9, 12 ]
Explanation. At index 6, "foobarthe" is a concatenation of "foo", "bar", "the". At index 9, "barthefoo" is a concatenation of "bar", "the", "foo". At index 12, "thefoobar" is a concatenation of "the", "foo", "bar".
[ "aaaaaa", "[\"a\",\"a\"]" ]
[ 0, 1, 2, 3, 4 ]
Explanation. The target substring length is 2. Every substring of length 2 from index 0 to 4 is "aa", which is a valid concatenation of two 'a's.
[ "wordgoodgoodgoodbestword", "[\"word\",\"good\",\"best\",\"word\"]" ]
[]
Explanation. The words to match are two "word"s, one "good", and one "best". No substring in `s` matches this exact concatenation.
[ "abcdefoohij", "[\"foo\"]" ]
[ 5 ]
Explanation. The substring "foo" is found at index 5.
[ "ababaababa", "[\"ab\",\"ba\",\"ab\"]" ]
[ 1 ]
Explanation. The target words are two "ab"s and one "ba". The substring `s[1:7]` is "babaab", which can be formed by concatenating "ba", "ab", "ab".
Follow-up: What is the time and space complexity of your solution? Can you suggest an alternative approach with different trade-offs?
1 <= s.length <= 10^4 1 <= words.length <= 5000 1 <= words[i].length <= 30 `words[i]` consists of lowercase English letters. All words in `words` have the same length. The sum of `words[i].length` over all `words[i]` will not exceed `10^4 - 1`.
- Views
- 12