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!
Someone can explain the Time complexity of Trie solution and DFS+Hash?

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 loopup dictionary from prefix to word index list takes O(NL^{2}) time. Any other way to achieve prefix to word list lookup can be substituted here.
 DFS recursion: The most conservative estimate will be up to a huge complexity O(N^{L}) depending on how commonly words are sharing letters in the given word list.
So the total time is O(NL^{2} + N^{L}).
Note that the time complexity for brute force would be O(N^{L}L^{2}).

@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(N^{L}) 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.


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