This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

Substrings that concatenate all the words

Given a string s and some words of the same length. Find the exact place in s where the substring can be formed by concatenating all the words in words.

Note that the substring must match exactly the words in the words, with no other characters in between, regardless of the order in which the words are concatenated in the words.

Tip:

  • 1 <= s.length <= 104
  • S consists of lowercase letters
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • Words [I] Consists of lowercase letters

In this case, we need to find all the substrings of the string that match the condition and return their starting position.

Since the substring needs to match exactly the words in words (both in content and in number), the words are given and all are of equal length, so it is clear that each substring has the same length, wordsNum (number of words) * wordsLength (length of word).

Therefore, we set the substring to a fixed length and iterate through the substring, assuming the word length is 3. The implementation is as shown in the figure:

We then need to determine whether the truncated substring meets the condition that the word is an exact match.

Since the word length is fixed, a sliding window of fixed length can be constructed to separate each word. The substring meets the condition by judging that all the words have appeared in the substring.

Note that each word may appear more than once in both the substring and the words, that the number of words cannot be more or less, and that it is a mistake to determine whether or not each word in the substring has appeared in the words (a mistake I made in the first place).

To count the number of words, you can use map: The word is key and the number of occurrences is value.

Save a map for the words in words, and build another map for each sliding window to count the number of words.

Every time a word is cut from a substring (as a key), a comparison is made to wordMap. If the value corresponding to the key in wordMap is 0 (that is, the word is not in words), then the substring does not qualify.

In addition, if you update the number of words and the number of words in the statistical map exceeds the number of words in the wordMap, you can also determine that the substring does not qualify (the number of words is too many).

func findSubstring(s string, words []string) []int {
    // Get the word length
    wordLength := len(words[0])
    wordNum := len(words)
    stringLenth := len(s)
    var ans []int
    // No words
    if wordNum == 0 {
        return ans
    }
    if stringLenth < wordLength {
        return ans
    }
    // Each word should appear the number
    wordMap := make(map[string]int)
    for _, word := range words {
        wordMap[word]++
    }
    // Build the sliding window
    for left := 0; left <= stringLenth - wordLength*wordNum; left++ {
        // Create a map to record the occurrence of the sliding window word
        tempMap := make(map[string]int)
        flag := true    // Record whether the substring is valid
        for right := left; right < left + wordLength*wordNum; right += wordLength {
            // Cut a word
            temp := s[right:right+wordLength]   
            if wordMap[temp] == 0 {
                // There is no such word
                flag = false
                break
            }
            // Add this word to the map
            tempMap[temp]++
            if wordMap[temp] < tempMap[temp] {
                // Too many words (too few may come later)
                flag = false
                break}}if flag {
            // Pass the test
            ans = append(ans, left)
        }
    }
    return ans
}
Copy the code

Submission result: