Someone can explain the Time complexity of Trie solution and DFS+Hash?


  • 0
    C

    So there are a lot of solutions to this problem, but when I saw these solutions, I am confused about the time complexity. Someone can explain? Thank you!


  • 0
    L

    I think it should be O(n^n). For every line, we would probably try every word to construct the final matrix. Imagine the word list is ['aaaa', 'aaab', 'aaac', .....]. Correct me if I am wrong.


  • 1

    I am glad you are also interested in the time complexity since I didn't see many posts to discuss this topic, either. I wrote a post here including my time complexity analysis for worst case.

    Let N be the number of words, and L be the length of each word.

    • Build loop-up dictionary from prefix to word index list takes O(NL2) time. Any other way to achieve prefix to word list look-up can be substituted here.
    • DFS recursion: The most conservative estimate will be up to a huge complexity O(NL) depending on how commonly words are sharing letters in the given word list.

    So the total time is O(NL2 + NL).

    Note that the time complexity for brute force would be O(NLL2).


  • 0

    @luofei said in Someone can explain the Time complexity of Trie solution and DFS+Hash?:

    I think it should be O(n^n). For every line, we would probably try every word to construct the final matrix. Imagine the word list is ['aaaa', 'aaab', 'aaac', .....]. Correct me if I am wrong.

    The DFS recursion alone should have up to O(NL) time complexity since each word square consists L rows of words with each picked from a list of size N. Note that the word list size N and each word length L are different, i.e., N ≥ L.


  • 0
    C

    @zzg_zzm
    Thanks, BTW, I saw you wrote a lot of solutions in yi mu san fen di.....LOL


  • 0

    @chnsht Yeah, it seems wired to post code there...but for me, coding itself could be a challenge as well, so tried to get as much practice as possible. Plus, I could benefit if someone happens to read and comment since some interview questions posted on 1point3acre are relatively new :-)


Log in to reply
 

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