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

• 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!

• 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.

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

• 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.

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

• @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 :-)

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