Problem description:

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.

Example:

1
2
3
4
5
6
7
8
9
10
Input: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

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

Solution:

For this question, we can start from thinking how to search multiple words in a 2D matrix.
Normally when we want to search multiple words, we’ll use unordered_map. But the given 2D matrix are lots of characters, so when we start searching one word, we need to know if the 2D matrix exist the next character of this word.

How do we instantly know the current character is invalid? HashMap?
How do we instantly know what’s the next valid character? LinkedList?
But the next character can be chosen from a list of characters. Mutil-LinkedList?
Combing them, Trie is the natural choice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# hastable and linked list to search word

class TrieNode:
    def __init__(self):
        self.dic = defaultdict(TrieNode)
        self.isWord = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        p = self.root
        for c in word:
            p = p.dic[c]
        p.isWord = True
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        trie = Trie()
        node = trie.root
        for word in words:
            trie.insert(word)
        
        for r in range(len(board)):
            for c in range(len(board[0])):
                self.dfs(res, board, r, c, node, "")
        return res
    def dfs(self, res, board, r, c, node, tmp):
        if node.isWord:
            res.append(tmp)
            node.isWord = False
        
        if r >= len(board) or c >= len(board[0]) or r < 0 or c < 0:
            return
        
        ch = board[r][c]
        if ch not in node.dic:
            return
        
        node = node.dic[ch]
        board[r][c] = '#'
        for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            self.dfs(res, board, r+x, c+y, node, tmp+ch)
        board[r][c] = ch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class TrieNode{
public:
    string word;
    vector<TrieNode*> next;
    TrieNode(): word(""), next(vector<TrieNode*>(26, nullptr)){}
};

class Solution {
public:
    TrieNode* buildTrie(vector<string>& words){
        TrieNode* root= new TrieNode();
        for(auto word: words){
            TrieNode* tmp= root;
            for(auto c: word){
                int i= c- 'a';
                if(tmp->next[i] == NULL)
                    tmp->next[i]= new TrieNode();
                tmp= tmp->next[i];
            }
            tmp->word= word;
        }
        return root;
    }
    
    void dfs(vector<vector<char>>& board, TrieNode* cur, int i, int j, vector<string>& res){
        if(i >= board.size() || j >= board[0].size() || i< 0 || j< 0) return;
        char c= board[i][j];
        if(c == '#' || cur->next[c-'a'] == nullptr) return;
        cur= cur->next[c-'a'];
        if(cur->word != ""){
            res.push_back(cur->word);
            cur->word= "";
        }
        
        board[i][j]= '#';
        dfs(board, cur, i+1, j, res);
        dfs(board, cur, i-1, j, res);
        dfs(board, cur, i, j+1, res);
        dfs(board, cur, i, j-1, res);
        board[i][j]= c;
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root= buildTrie(words);
        vector<string> res;
        for(int i= 0; i< board.size(); i++){
            for(int j= 0; j< board[0].size(); j++){
                dfs(board, root, i, j, res);
            }
        }
        return res;
    }
};

time complexity: $O()$
space complexity: $O()$
reference: