day107（3.8）——leetcode面试经典150

212. 单词搜索 II

直接用最暴力的方法解的

212. 单词搜索Ⅱ

题目：

题解：

class Solution { //创建结果集 List<String> res = new ArrayList<>(); //HashSet（无序、最快）或 TreeSet（有序） //创建set容器，并将words中的元素都加入 Set<String> set = new HashSet<>(); int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; //同一个单元格内的字母在一个单词中不允许被重复使用，所以创建visited数组来记录已经访问过的位置 boolean[][] visited = new boolean[15][15]; char[][] _board; public List<String> findWords(char[][] board, String[] words) { // 数据范围只有 12，且 words 中出现的单词长度不会超过 10，可以考虑使用「回溯算法」。 // 起始先将所有 words 出现的单词放到 Set 结构中，然后以 board 中的每个点作为起点进行爆搜（由于题目规定在一个单词中每个格子只能被使用一次，因此还需要一个 vis 数组来记录访问过的位置）： // 如果当前爆搜到的字符串长度超过 10，直接剪枝； // 如果当前搜索到的字符串在 Set 中，则添加到答案（同时了防止下一次再搜索到该字符串，需要将该字符串从 Set 中移除）。 _board = board; for(String word:words) { set.add(word); } //遍历每一个元素，进行爆搜 for(int i=0;i<board.length;i++) { for(int j=0;j<board[0].length;j++) { if(visited[i][j]==false) { //表示已经开始访问 visited[i][j]=true; //创建StringBuilder用来更新每一步走到的字符 StringBuilder sb = new StringBuilder(); sb.append(board[i][j]); //进行爆搜 dfs(i,j,sb); //回溯 visited[i][j]=false; sb.deleteCharAt(sb.length()-1); } } } return res; } void dfs(int x, int y, StringBuilder sb) { //因为单词最长长度就是为10 if(sb.length()>10) { return ; } //判断set中是否包含该单词 if(set.contains(sb.toString())) { //将单词加入结果集中 res.add(sb.toString()); //为了防止重复加入，直接将该单词从set集合中删除 set.remove(sb.toString()); } //走下一步 for(int[] dir:dirs) { int dx=x+dir[0],dy=y+dir[1]; if(dx<0||dx>=_board.length||dy<0||dy>=_board[0].length) { continue; } if(visited[dx][dy]==true) { continue; } visited[dx][dy]=true; //改变sb sb.append(_board[dx][dy]); //继续递归 dfs(dx,dy,sb); visited[dx][dy]=false; sb.deleteCharAt(sb.length()-1); } } }