leetcod212hard单词搜搜II回溯

旧城等待， 2023-07-09 02:18 34阅读 0赞

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

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

输出: \[“eat”,“oath”\]

在一个二维网格里搜索，思路就是深度优先搜索。上下左右方向判断满足吗？满足继续搜索，当单词找到后加入结果集中，那么合适的剪枝能加快搜索速度，以及防止节点被重复遍历就剪枝。都是需要考虑到的。

直接看代码把。

class Solution {
        
     class TrieNode {
        
           
            TrieNode[] next;
            String word;
            public TrieNode() {
        
                this.next = new TrieNode[26];
            }
        }   
        public List<String> findWords(char[][] board, String[] words) {
        
                List<String> res = new ArrayList<>();
                // 初始化
                TrieNode root = buildTree(words);
    
                for (int i = 0;i < board.length;i++) {
        
                    for (int j = 0;j < board[0].length;j++) {
                    
                            dfs(board,i,j,res,root);
                    }
                }
                    
                return res;
        }
    
        public void dfs(char[][] board,int i,int j,List<String> res,TrieNode root) {
        
                // 剪枝,trie不满足就剪枝return
                char c = board[i][j];
                if (board[i][j] == '*' || root.next[c - 'a'] == null) return;
                root = root.next[c - 'a'];
                if (root.word != null) {
        
                    res.add(root.word);
                    root.word = null;
                     // 刚开始加了return死活最后一个过去不，原因是return 提前，防止后续进行递归了，但是没考虑出一种情况就是 anes,anesit这样的，如果提前找到一个就return，就导致后续以这个为前缀的树就找不到了。
                }
    
                // 来到这就证明存在Trie树中，需要进行dfs， dfs前做什么？后做什么？
                // 加标志的目的是什么？ 答案是防止重复遍历到,可以剪枝
                board[i][j] = '*';
    
                // 这里就是深层递归的逻辑
                // 加上判断性条件 满足都的单个的i,可能
                if (i > 0) dfs(board,i-1,j,res,root);
                if (j > 0) dfs(board,i,j-1,res,root);
                if (i < board.length-1) dfs(board,i+1,j,res,root);
                if (j < board[0].length-1) dfs(board,i,j+1,res,root);
    
                board[i][j] = c;
        }
    
        public TrieNode buildTree(String[] words) {
        
    
            TrieNode root = new TrieNode();
    
            for (String word:words) {
        
                TrieNode head = root;
                char[] wordchar = word.toCharArray();
                int index = 0;
                for (int i = 0;i < wordchar.length;i++) {
        
                    if (head.next[wordchar[i]-'a'] == null)
                        head.next[wordchar[i]-'a'] = new TrieNode();
                    head = head.next[wordchar[i]-'a'];
                }
                head.word = word;
            }
            return root;
        }
    
    }

同时这里有个小技巧。 这样加判断条件，比每次都去遍历i，j坐标位置的不满足要好太多了。原因是，通过直接调用的dfs 每次都被限制了不越界。  
而dfs本身的递归调用，通过i,j 合法坐标 --> 判断i合法进行（i+1,j ）所以也是合法的。.

if (i > 0) dfs(board,i-1,j,res,root);
                if (j > 0) dfs(board,i,j-1,res,root);
                if (i < board.length-1) dfs(board,i+1,j,res,root);
                if (j < board[0].length-1) dfs(board,i,j+1,res,root);

test