Why we use a trie here? Is it used because there are way more words in the dictionary?


  • 1
    P

    Because the normal backtracking gave me an error (stack overflow) here.


  • 4
    H

    Why we use trie here? Because we may add several words in one backtracking, say "aa" and "aab". By looking up TrieNode, you can continue your search after you found "aa" instead of starting a new search.


  • 0
    C

    Because when you start from any point on that board, and walk around to construct all possible words, you ARE basically constructing a Trie with that starting point as the root. By using a reference Trie as your candidate words storage, you explore matching paths of the two trees.

    Because you need to exhaust the matches, the time complexity is at least that of visiting all the matching paths on the board Trie, and making the words also a Trie will make the total time complexity stay at that minimum level.


  • 0
    D

    @Chomolungma This is a good explanation! Since DFS will construct a trie anyway, letting the reference trie help the DFS process will make it optimal.


  • 0
    S

    @hpplayer Hi, hpplayer, theoretically, how about this big O time complexity? Thanks!


Log in to reply
 

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