# Replace Words

• What if there are multiple space between words?

• this is fuck hard

• For the second method using Trie, Why is time complexity O ( n ) ?
For each word in the sentence, we search through the trie every-time and
time require required to search in trie is O ( length of the word ), shouldn't it be

• Total time complexity = O ( total_words_in_sentence * avg_length_of_word )

• I don't get it. Why Method #1 is O(w^2) instead of O(w)? Basically for each word we just traverse once. Worst case we traverse every single character of the sentence. Which is O(n). contain() is constant time.

• @apk `Total time complexity = O ( total_words_in_sentence * avg_length_of_word )` is nothing but O(N) where N is the length of the sentence. So both the answers are correct.

For e.g. if sentence is = "the cat rat and bat"
Number of words = 5
avg length of words = 3
And 5 * 3 = 15, nothing but O(N).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.