Replace Words


  • 0

    Click here to see the full article post


  • 0
    I

    What if there are multiple space between words?


  • 0
    Z

    this is fuck hard


  • 0
    A

    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 )

  • 1
    G

    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.


  • 0
    S

    @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).


Log in to reply
 

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