This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Given a string s and some words of the same length. Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.

Note that the substring must match exactly the words in words, without any other characters in the middle, but you do not need to consider the sequence in which words are concatenated.

  • Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting from index 0 and 9 are "barfoo" and "foobar", respectively. The order of the outputs is not important, [9,0] is also a valid answer.Copy the code
  • Example 2:
Input: s = "wordgoodGoodGoodBestWord ", words = ["word","good","best","word"] output: []Copy the code
  • Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] output: [6,9,12]Copy the code
  • Tip:
1 <= S. length <= 104 s Lowercase letters 1 <= words.length <= 5000 1 <= Words [I]. Length <= 30 Words [I] Lowercase lettersCopy the code

Implementation approach

Each word in the words array is the same length. Let’s call it wiLength. In this way, we can first obtain the string length wLength of all words in words and then intercept the string length of wLength in S to extract the same number of words according to the length of wiLength. In this way, there are two word lists. As long as the two word lists are the same, it is ok. If so, add the starting position of the screenshot string left to res, and return RES by traversing S until the truncated length is less than wLength.

/ * * *@param {string} s
 * @param {string[]} words
 * @return {number[]}* /
var findSubstring = function(s, words) {
    let res = []
    let wiLength = words[0].length
    let wLength = words.join(' ').length
    if (s.length < wLength) return res
    let wMap = new Map(a)for (let item of words) {
        let count = wMap.get(item) ? wMap.get(item) + 1 : 1
        wMap.set(item, count)
    }
    let left = 0
    let str = s.substr(left, wLength)
    while(str.length == wLength) {
        if (fn(str)) {
            res.push(left)
        }
        left++
        str = s.substr(left, wLength)
    }
    return res

    function fn (str) {
        let sMap = new Map(a)for (let i = 0; i < wLength; i+=wiLength) {
            let item = str.substr(i, wiLength)
            let count = sMap.get(item) ? sMap.get(item) + 1 : 1
            sMap.set(item, count)
        }
        for (let item of wMap.keys()) {
            if(sMap.get(item) ! = wMap.get(item)) {return false}}return true}};Copy the code