educative.io

Educative

I used the same idea as find_permutation problem

Think that a word in the list is a character, so the code is similar to find_permutation problem…

function find_word_concatenation(str, words) {
    const result_indices = []
    let start = 0,
        matched = 0,
        wordLength = words[0].length,
        wordsFrecuency = {};

    for (const word of words) {
        if (!(word in wordsFrecuency))
            wordsFrecuency[word] = 0

        wordsFrecuency[word]++
    }

    for (let end = wordLength-1; end < str.length; end = end + wordLength) {
        const rightWord = str.substring(end - wordLength + 1, end + 1)

        if (rightWord in wordsFrecuency) {
            wordsFrecuency[rightWord]--

            if (wordsFrecuency[rightWord] === 0) {
                matched++
            }
        }

        if (matched === Object.keys(wordsFrecuency).length) {
            result_indices.push(start)
        }

        if (end >= (wordLength * 2) - 1) {
            leftWord = str.substring(start, start + wordLength)
            start += wordLength

            if (leftWord in wordsFrecuency) {
              if (wordsFrecuency[leftWord] === 0) {
                matched -= 1
              }

              wordsFrecuency[leftWord] += 1
            }
        }
    }

    return result_indices
}

I did the same, though in Python. It is easier that way.

What will be the Time Complexity of this Algorithm? I think it will be smaller than the given in the Solution?
please explain.

1 Like