leetcode 212. Word Search II | 212. 单词搜索 II（Trie，回溯，DFS）

客官°小女子只卖身不卖艺 2022-09-15 00:56 170阅读 0赞

## 题目 ##

[https://leetcode.com/problems/word-search-ii/][https_leetcode.com_problems_word-search-ii]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

基于前缀树实现，如果把 Trie 也看做一个特殊的图的话，就是 **将两个图同时进行 dfs**，就像判断两个树是否相同那样。

可以参考：[leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java）][leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java] 中的数据结构，然后改造一下即可。

class Node { 
        Node[] map;
        boolean isEnd;
    
        public Node() { 
            this.map = new Node['z' - 'a' + 1];
        }
    
        public Node get(char c) { 
            return map[c - 'a'];
        }
    
        public Node put(char c) { 
            Node node = new Node();
            map[c - 'a'] = node;
            return node;
        }
    }
    
    class Trie { 
        Node node;
    
        public Trie() { 
            node = new Node();
        }
    
        public void insert(String word) { 
            char[] chars = word.toCharArray();
            Node cur = node;
            for (int i = 0; i < chars.length; i++) { 
                if (cur.get(chars[i]) != null) { 
                    cur = cur.get(chars[i]);
                } else { 
                    cur = cur.put(chars[i]);
                }
                if (i == chars.length - 1) { 
                    cur.isEnd = true;
                }
            }
        }
    }
    
    
    class Solution { 
        int M, N;
        List<String> result;
    
        public List<String> findWords(char[][] board, String[] words) { 
            M = board.length;
            N = board[0].length;
            result = new ArrayList<>();
    
            Trie trie = new Trie();
            for (String s : words) { 
                trie.insert(s);
            }
            boolean[][] visited = new boolean[M][N];
            for (int k = 0; k < trie.node.map.length; k++) { 
                if (trie.node.map[k] == null) continue;
                // word can start from any location on board
                for (int i = 0; i < M; i++) { 
                    for (int j = 0; j < N; j++) { 
                        dfs(board, i, j, visited, trie.node.map[k], (char) (k + 'a'), String.valueOf((char) (k + 'a')));
                    }
                }
            }
            return result;
        }
    
        public void dfs(char[][] board, int i, int j, boolean[][] visited, Node node, char val, String path) { 
            if (i < 0 || i == M || j < 0 || j == N || visited[i][j] || board[i][j] != val) return;
            if (node.isEnd) { 
                result.add(path);
                node.isEnd = false; // 避免相同前缀的字符串被多次添加到result中
            }
    
            visited[i][j] = true;
            for (int k = 0; k < node.map.length; k++) { 
                Node next = node.map[k];
                if (next != null) { 
                    dfs(board, i + 1, j, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                    dfs(board, i - 1, j, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                    dfs(board, i, j + 1, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                    dfs(board, i, j - 1, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                }
            }
            visited[i][j] = false;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_word-search-ii]: https://leetcode.com/problems/word-search-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e2248c7fa4884a01bcd47b3299b76858.png
[leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java]: https://blog.csdn.net/sinat_42483341/article/details/117767824
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/b7fc5df739864b388e7531fd9abe2dfe.png