Click here to see the full article post
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.
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.