从零学算法212

本文主要是介绍从零学算法212，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

212.给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：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：
输入：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 * 10⁴
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

这里我首先想到的是遍历所有 words，然后再遍历所有 board 尝试每个字符作为起点能否得到某个 word，但是超时了，这里可以转换思路，遍历所有 board，得到以每个字符开始，组成字符串的所有可能性，然后看是否在 words 中，是就加入结果列表 res

  // 方向数组int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};char[][] board;int m,n;// 存储 words 中的 wordSet<String> set = new HashSet<>();// 记录 board 中每个字符是否已使用boolean[][] visit = new boolean[12][12];// 结果列表List<String> res = new ArrayList<>();public List<String> findWords(char[][] _board, String[] words) {board = _board;m= board.length;n= board[0].length;for(String s:words)set.add(s);StringBuilder sb = new StringBuilder();// 尝试所有字符为起点得到可能的路径for(int i=0;i<m;i++){for(int j=0;j<n;j++){visit[i][j]=true;sb.append(board[i][j]);dfs(i,j,sb);visit[i][j] = false;sb.deleteCharAt(sb.length() - 1);}}return res;}void dfs(int i, int j, StringBuilder sb) {// 因为 word 长度至多为 10 所以再往后就不找了if(sb.length() > 10)return;// 当前路径在 set 中就得到一个结果，记得去除 set 中该路径if(set.contains(sb.toString())){res.add(sb.toString());set.remove(sb.toString());}for(int[] d : dirs){int x = i + d[0];int y = j + d[1];if(x < 0 || x >= m || y < 0 || y >= n)continue;if(visit[x][y])continue;visit[x][y] = true;sb.append(board[x][y]);dfs(x, y, sb);visit[x][y] = false;sb.deleteCharAt(sb.length() - 1);}}

上述解法只在当前搜索路径达到 10 才进行剪枝，为了优化为每一步搜索都剪枝，我们可以使用前缀树（Trie），可以参考力扣 208 题的题解，我也趁此学习完记录了一下。该题解原文中也包含了前缀树的讲解。
这里我们把 isEnd 直接替换为一个 String 类型的变量 s，记录该尾字符对应的字符串。我们创建一个前缀树，将 word 都存入其中，然后遍历 borad 每个字符作为起点，如果前缀树的根节点的子节点都不包含该字符，那就都不用 dfs 了直接下一位。
dfs 过程如果遇到了 s 不为 null 的情况，表示 board 存在路径对应 s（也就是 word），那就加入 set，因为 dfs 过程中可能不止一次找到该字符串，所以先用 set 记录，最后遍历添加到 res 即可。

  class Solution {class TrieNode {String s;TrieNode[] tns = new TrieNode[26];}void insert(String s) {TrieNode p = root;for (char c:s.toCharArray()) {int u = c - 'a';if (p.tns[u] == null) p.tns[u] = new TrieNode();p = p.tns[u];}p.s = s;}int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};char[][] board;int m,n;Set<String> set = new HashSet<>();boolean[][] visit = new boolean[12][12];List<String> res = new ArrayList<>();TrieNode root = new TrieNode();public List<String> findWords(char[][] _board, String[] words) {board = _board;m= board.length;n= board[0].length;for(String s:words)insert(s);for(int i=0;i<m;i++){for(int j=0;j<n;j++){int u = board[i][j] - 'a';// 前缀树中有字符串以当前字符开头才寻找路径if(root.tns[u] != null){visit[i][j]=true; dfs(i,j,root.tns[u]);visit[i][j] = false;}}}for(String s:set)res.add(s);return res;}void dfs(int i, int j, TrieNode node) {// 因为每一步都合法，所以只要能找到这一步就加入 setif(node.s != null)set.add(node.s);for(int[] d : dirs){int x = i + d[0];int y = j + d[1];if(x < 0 || x >= m || y < 0 || y >= n)continue;if(visit[x][y])continue;int u = board[x][y] - 'a';// 之前是写死了长度大于 10 则停止搜索// 而这里只要当前字符不在 word 的需求中就停止搜索// 比如 words 为 [abcd,accd,adcd]，当前字符搜索到了前缀树第二层// 前缀树第二层包含了 [b,c,d]，可如果当前字符是比如 e，那就不需要再找了// ae*** 无论如何都不会在 words 中if(node.tns[u] != null){visit[x][y] = true;dfs(x, y, node.tns[u]);visit[x][y] = false;}}}}