LeetCode_前缀树_困难_212.单词搜索 II

╰半橙微兮° 2023-10-12 13:53 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

**示例 1：**

![在这里插入图片描述][4fe2eeaf34b1446eb27fbd99597ba938.png]

输入：board = \[\[“o”,“a”,“a”,“n”\],\[“e”,“t”,“a”,“e”\],\[“i”,“h”,“k”,“r”\],\[“i”,“f”,“l”,“v”\]\], words = \[“oath”,“pea”,“eat”,“rain”\]  
输出：\[“eat”,“oath”\]

**示例 2：**

![在这里插入图片描述][8b5fd9a5e30d4a62ac34d90feb0a9ad9.png]  
输入：board = \[\[“a”,“b”\],\[“c”,“d”\]\], words = \[“abcb”\]  
输出：\[\]

**提示：**  
m == board.length  
n == board\[i\].length  
1 <= m, n <= 12  
board\[i\]\[j\] 是一个小写英文字母  
1 <= words.length <= 3 \* 104  
1 <= words\[i\].length <= 10  
words\[i\] 由小写英文字母组成  
words 中的所有字符串互不相同

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/word-search-ii

## 2.思路 ##

（1）回溯  
本题可以在[79.单词搜索][79.]这题的之上，对 words 中的所有 word 进行判断即可，最终结果保存到 res 中。但是该方法的时间复杂度较高，因此在 LeetCode 中提交时会显示“超出时间限制”的提示！

（2）回溯 & 字典树  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_回溯\_中等\_79.单词搜索][79.]

## 3.代码实现（Java） ##

//思路1————回溯
    class Solution {
        
    
        //定义上、下、左、右这 4 个方向
        int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
    
        public List<String> findWords(char[][] board, String[] words) {
        
            List<String> res = new ArrayList<>();
            for (String word : words) {
        
                if (exist(board, word)) {
        
                    res.add(word);
                }
            }
            return res;
        }
    
        public boolean exist(char[][] board, String word) {
        
            int m = board.length;
            int n = board[0].length;
            /*
                visited[i][j] == true 表示在每一轮搜索中，字符 board[i][j] 已经访问过了
                此处的每一轮搜索指的是以二维字符网格 board 中的每一个字符作为起点开始搜索，当每访问一个字符 board[i][j]，
                就将 visited[i][j] 设置为 true，当该轮搜索结束后，再将 visited[i][j] 设置为 false
            */
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    //遍历二维字符网格 board，每遇到一个字符 board[i][j]，就以它为起点开始搜索 word
                    if (judge(i, j, word, 0, board, visited)) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    
        /* 
            i、j: 表示当前正在访问的二维字符网格中字符的横坐标和纵坐标
            k: 表示匹配 word 中字符的下标
        */
        public boolean judge(int i, int j, String word, int k, char[][] board, boolean[][] visited) {
        
            if (board[i][j] != word.charAt(k)) {
        
                return false;
            } else if (word.length() - 1 == k) {
        
                // word 的每一个字符都已匹配成功，即 word 存在于网格中，返回 true
                return true;
            }
            //字符 board[i][j] 在此轮搜索中已经被访问过
            visited[i][j] = true;
            boolean flag = false;
            //分别向 4 个方向开始搜索
            for (int[] dir : dirs) {
        
                int newi = i + dir[0];
                int newj = j + dir[1];
                if (newi >= 0 && newj >= 0 && newi < board.length && newj < board[0].length) {
        
                    if (!visited[newi][newj] && judge(newi, newj, word, k + 1, board, visited)) {
        
                        flag = true;
                        break;
                    }
                }
            }
            //本轮搜索结束
            visited[i][j] = false;
            return flag;
        }
    }

//思路2————回溯 & 字典树
    import java.util.*;
    
    class Solution {
        
        //定义上、下、左、右这 4 个方向
        int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
        int m, n;
    
        public List<String> findWords(char[][] board, String[] words) {
        
            m = board.length;
            n = board[0].length;
            Trie trie = new Trie();
            for (String word : words) {
        
                trie.insert(word);
            }
            Set<String> res = new HashSet<>();
            //遍历整个 board
            for (int i = 0; i < m; ++i) {
        
                for (int j = 0; j < n; ++j) {
        
                    dfs(board, trie, i, j, res);
                }
            }
            return new ArrayList<>(res);
        }
    
        public void dfs(char[][] board, Trie curTrie, int i, int j, Set<String> res) {
        
            if (!curTrie.children.containsKey(board[i][j])) {
        
                return;
            }
            char c = board[i][j]; 
            curTrie = curTrie.children.get(c);
            if (!"".equals(curTrie.word)) {
        
                res.add(curTrie.word);
            }
            board[i][j] = '#';
            for (int[] dir : dirs) {
        
                int nextI = i + dir[0];
                int nextJ = j + dir[1];
                //判断边界条件
                if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n) {
        
                    dfs(board, curTrie, nextI, nextJ, res);
                }
            }
            board[i][j] = c;
        }
    }
    
    class Trie {
        
        String word;
        Map<Character, Trie> children;
    
        public Trie() {
        
            this.word = "";
            this.children = new HashMap<>();
        }
    
        public void insert(String word) {
        
            Trie cur = this;
            for (int i = 0; i < word.length(); ++i) {
        
                char c = word.charAt(i);
                if (!cur.children.containsKey(c)) {
        
                    cur.children.put(c, new Trie());
                }
                cur = cur.children.get(c);
            }
            cur.word = word;
        }
    }

[4fe2eeaf34b1446eb27fbd99597ba938.png]: https://img-blog.csdnimg.cn/4fe2eeaf34b1446eb27fbd99597ba938.png
[8b5fd9a5e30d4a62ac34d90feb0a9ad9.png]: https://img-blog.csdnimg.cn/8b5fd9a5e30d4a62ac34d90feb0a9ad9.png
[79.]: https://blog.csdn.net/weixin_43004044/article/details/119976643
[Link 1]: https://leetcode.cn/problems/word-search-ii/solution/dan-ci-sou-suo-ii-by-leetcode-solution-7494/