educative.io

Solution with O(N+M) time

Courses
,
#1

I think I found a solution that uses the Sliding Window approach with O(N+M) time instead of O(N * M * Length)

   def find_word_concatenation(string, words):
     result_indices = []
     if len(words) == 0 or len(words[0]) == 0:
       return []

     #Get hashmap of word frequencies
     word_frequencies = {}
     for word in words:
       if word in word_frequencies:
         word_frequencies[word] += 1
       else:
         word_frequencies[word] = 1

     #Start_index keeps track of the start of a new word
     window_start, matched, start_index = 0, 0, 0
     word_length = len(words[0])

     for window_end in range(len(string)):
       if string[start_index: window_end + 1] in word_frequencies:
         word_frequencies[string[start_index: window_end + 1]] -= 1
       if word_frequencies[string[start_index: window_end + 1]] == 0:
         matched += 1
       start_index = window_end + 1

      if matched == len(word_frequencies):
        result_indices.append(window_start)
        word_frequencies[string[window_start: window_start + word_length]] += 1
        matched -= 1
        window_start += word_length

      #If the length the current window is larger than the length of 2 words
  # We know that soomething is wrong, so we move the start_index pointer to the second word in the window
      if window_end - window_start + 1 > word_length * 2:
        if string[window_start: window_end - word_length] in word_frequencies:
         word_frequencies[string[window_start: window_start + word_length]] += 1
        if word_frequencies[string[window_start: window_start + word_length]] != 0:
          matched -= 1
        window_start += word_length
        start_index = window_end

    return result_indices

Sorry for the bad formatting XD. Let me know if I missed something.