educative.io

Educative

Optimizing with trie?

I wonder why the time complexity has to be O(N∗M∗Len) (where ‘N’ is the number of characters in the given string, ‘M’ is the total number of words, and ‘Len’ is the length of a word).
It seems to me that the term ‘M’ can be removed by using a trie to check if any of the M words appear in a given location in the string using only Len steps (as opposed to M*Len the way the solution is implemented).
Thanks :slight_smile:
Guy

Correction: a trie is not really any better complexity-wise than checking if a word is in a dictionary.

But the time complexity can still be improved to O(N*Len). The proposed solution does redundant work by looking for a complete concatenation at each step instead of using a sliding window to re-use some of the previous word matches.

Here is my proposed solution:

def find_word_concatenation(str, words):
  wlen = len(words[0])

  # calculate word frequencies
  wfreq = {}
  for w in words:
    wfreq.setdefault(w,0)
    wfreq[w] += 1

  result_indices = []

  for phase in range(wlen):
    matched_words = []
    match_start = phase

    for i in range(phase, len(str), wlen):
      word = str[i:i+wlen]

      if word in wfreq:
        # word match found!
        matched_words.append(word)
        wfreq[word] -= 1

        if wfreq[word] == 0 and len(matched_words) == len(words):
          # complete match found!
          result_indices.append(match_start)

        while wfreq[word] < 0 or len(matched_words) == len(words):
          # oops, too many occurences (or match found), shrink window
          word2 = matched_words.pop(0)
          wfreq[word2] += 1
          match_start += wlen

      else:
        # no match, clear everything
        for word2 in matched_words:
          wfreq[word2] += 1
        matched_words = []
        match_start = i + wlen

  return result_indices

matched_words is not necessary but it makes the code a little easier to read.

Please let me know if I’m missing anything :slight_smile:

Hey Guy,

I’m glad you mentioned this because I had the same idea. I believe you actually CAN improve the runtime with a Trie. I did so myself, bringing the suggested runtime from O(N * W * Len) to O(N + W * Len) (Notice the +) :slight_smile:. For the solution to actually have better performance characteristics, you have to use a counting strategy similar to the one used in the Problem Challenge 2.

See my Javascript implementation (There are a couple moving pieces but let me know if you’d like me to explain further):

/**
 * W = number of words
 * w = word size
 * Space: O(W * w)
 * Time: O(N + (W * w))
 * 
 */

const createWordTrie = (words) => {
  const trie = {value: null, children: new Map() };
  let current = trie;
  for (const word of words) {
    for (const char of word) {
      const nextNode = current.children.get(char) || {value: null, children: new Map() };
      current.children.set(char, nextNode);
      current = nextNode;
    }
    current.value = current.value ? current.value + 1 : 1;
    current = trie;
  }
  return trie;
}
const find_word_concatenation = function(str, words) {
  const indices = [];
  const singleWordSize = words[0].length;
  const numberOfWords = words.length;
  const wordsSize = singleWordSize * words.length;
  const wordsTrie = createWordTrie(words);

  let windowStart = 0;
  let matches = 0;

  let frontTrieHead = wordsTrie;
  let backTrieHead = wordsTrie;

  for (let windowEnd = 0; windowEnd < str.length; windowEnd ++) {
    const char = str[windowEnd];

    if (frontTrieHead.children.has(char)) {
      frontTrieHead = frontTrieHead.children.get(char);
      if (frontTrieHead.value !== null) {
        frontTrieHead.value--;

        if (frontTrieHead.value === 0) {
          matches++;
        }

        frontTrieHead = wordsTrie;
      }
    } else {
       frontTrieHead = wordsTrie;
    }

    if (windowEnd >= wordsSize) {
      const startChar = str[windowStart];
      if (backTrieHead.children.has(startChar)) {
        backTrieHead = backTrieHead.children.get(startChar);

        if (backTrieHead.value !== null) {
          if (backTrieHead.value === 0) {
            matches--;
          }

          backTrieHead.value++;
          backTrieHead = wordsTrie
        }
      } else {
        backTrieHead = wordsTrie;
      }

      windowStart++;
    }

    if (matches === numberOfWords && backTrieHead === wordsTrie && frontTrieHead === wordsTrie) {
      indices.push(windowStart);
    }
  }

  return indices;
};