Title Description:
Given a string s and an array of strings words, all strings in wordsEqual length 。
A concatenated substring in s is a string that contains all the strings in words.Substrings connected in any order of arrangement。
For example, if words = ["ab", "cd", "ef"], then "abcdef", "abefcd", "cdabef", "cdabef", "efabcd", and "efcdab" are concatenated substrings. "acdbef" is not a tandem substring because it is not a concatenation of any words arrangement.
Returns the starting index of all concatenated substrings in s. You can return answers in any order. You can return the answers in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Output: [0,9]
Explanation: since == 2 while words[i].length == 3, the length of the concatenated substring must be 6.
The substring "barfoo" starts at position 0. It is a concatenation of words in the order ["bar", "foo"].
The substring "foobar" starts at position 9. It is a concatenation of words in the order ["foo", "bar"].
The order of output is irrelevant. Returning [9,0] is also possible.
Title Analysis:
The question wants to find the start subscripts of all permutations of the strings of the character array in s. Note that the title mentions labeling all conditions where the lengths of the strings of the character array have the same length. Set this condition is naturally useful, if the length of the strings are not the same, then only to find all possible strings, and then go to match in s. But the length of the same, you can use a fixed size sliding window to solve, as long as the consecutive occurrences of the string can be covered by all the words, that is, to find success. How to determine whether the word occurs ==> through the word frequency for statistics.
Input: string s, string array words
Output: subscripts of all permutations of characters in words starting in s
Condition: all strings in words have the same length 1 <= <= 10⁴
Click to view code
func findSubstring(s string, words []string) []int {
if len(words) == 0 || len(s) < len(words)*len(words[0]) {
return []int{}
}
wordsCount := make(map[string]int)
for _, word := range words {
wordsCount[word]++
}
wordLen := len(words[0])
totalWords := len(words)
res := []int{}
for i := 0; i < wordLen; i++ {
left := i
count := 0
windowCount := make(map[string]int)
for right := i; right <= len(s)-wordLen; right += wordLen {
word := s[right : right+wordLen]
if _, exists := wordsCount[word]; exists {
windowCount[word]++
count++
for windowCount[word] > wordsCount[word] {
leftWord := s[left : left+wordLen]
windowCount[leftWord]--
count--
left += wordLen
}
if count == totalWords {
res = append(res, left)
}
} else {
windowCount = make(map[string]int)
count = 0
left = right + wordLen
}
}
}
return res
}
Solution two.
Following the question, get all the permutations of the words and then put each word into s to find out if it exists.