- 22.8%

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

1 | For example, |

Note:

You may assume that all inputs are consist of lowercase letters a-z.

https://discuss.leetcode.com/topic/14301/my-c-trie-backtrace-based-solution-48-ms

My C++ Trie + Backtrace based solution (48 ms)

The idea is to use a Trie to build a prefix tree for words to simplify the search and do DFS to search all the possible strings.

For Trie, 26 pointers to point the sub-strings and a bool leaf to indicate whether the current node is a leaf (i.e. a string in words) and also idx is used to save the index of words for the current node.

For DFS, just check if the current position is visited before (board[i][j]==’X’), if so, return, check if there is a string with such prefix (nullptr == root->children[words[idx][pos]-‘a’]), if not, return; otherwise, check if the current searched string is a leaf of the trie (a string in words), if so, save it to res and set leaf of the trie node to false to indicate such string is already found. At last, move to its neighbors to continue the search. Remember to recover the char [i][j] at the end.

1 | class Solution { |

Based on the comments received. I created another version with Trie node counter (thanks, zhiqing_xiao and gxyeecspku). However, for the current test set, it doesn’t help too much. Anyway, my version with Trie node counter.

1 | class Solution { |

https://discuss.leetcode.com/topic/20210/my-ac-very-clean-c-code

My AC very clean C++ code

The idea is start from every position of the board, and then see if we can find a word starting from this position with checking if is_end is true in TrieNode structure

1 | class TrieNode{ |

https://discuss.leetcode.com/topic/14307/27-lines-uses-complex-numbers

27 lines, uses complex numbers

I first build the tree of words with root root and also represent the board a different way, namely as one-dimensional dictionary where the keys are complex numbers representing the row/column indexes. That makes further work with it easier. Looping over all board positions is just for z in board, the four neighbors of a board position z are just z + 1j**k (for k in 0 to 3), and I don’t need to check borders because board.get just returns “None” if I request an invalid position.

After this preparation, I just take the tree and recursively dive with it into each board position. Similar to how you’d search a single word, but with the tree instead.

1 | class Solution: |

https://discuss.leetcode.com/topic/16782/python-code-use-trie-and-dfs-380ms

Python code use trie and dfs 380ms

1 | class Solution: |

https://discuss.leetcode.com/topic/22858/python-dfs-solution-directly-use-trie-implemented

Python dfs solution (directly use Trie implemented).

Here is an implementation based on Implement Trie in LeetCode. TrieNode, Trie, Solution are treated as seperated classes.

1 | class TrieNode(): |

19ms, 90.34%, September 23, 2016

https://discuss.leetcode.com/topic/9826/my-19ms-accepted-c-code

1 | class Solution { |

47ms, September 23, 2016

https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space

1 | public class Solution { |