[Leetcode学习-java]Word Search II(二维数组找相同字符串)

问题：

难度：Hard

说明：

给出二维数组arr，以及一个需要匹配的字符串数组strArr，然后在arr其中找到strArr的字符，需要是数组内连续的字符串，不限制方向，但是匹配时候只能用一次，题目确实比较绕，不过题意如此。

问题链接：https://leetcode.com/problems/word-search-ii/

相关算法：

P1002-过河卒：https://blog.csdn.net/qq_28033719/article/details/106261183

输入案例：

Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"] // o - a - t - h从(0,0) - (0,1) - (1,1) - (2,1) // e - a - t从(3,1) - (2,1) - (1,1) Output: ["eat","oath"]

我的代码：

相对来说比较困难，我一开始以为用Rabin-Karp算法，但是发现运算量会很大，而且也吃内存。

看提示就说用字典树，我开始用字典树给二维数组打（疯了），然后换成给strArr弄成字典树就好。

然后就是常见的图形搜索，用DFS，DFS用递归，二维数组DFS的坐标比较适合递归处理。

class Solution { static int x; static int y; // 结果集并且用hash去重 HashSet<String> set; static char[][] board2; public List<String> findWords(char[][] board, String[] words) { // 将words全部存入字典树 Tree root = new Tree(); board2 = board; words2 = words; for(int i = 0;i < words.length;i ++) { String str = words[i]; Tree tree = root; for(char ch : str.toCharArray()) { int index = ch - 'a'; Tree next = tree.next[index] == null ? new Tree() : tree.next[index]; tree.next[index] = next; tree = next; } tree.end = true; tree.index = i; } // 将二维数组遍历一遍 set = new HashSet<String>(); x = board2.length; y = board2[0].length; int c = x * y; for(int i = 0;i < x;i ++) { for(int j = 0;j < y;j ++) { int index = board2[i][j] - 'a'; if(root.next[index] != null) { // 为了不重复利用，设置参观表 boolean[][] visited = new boolean[x][y]; search(root,index, i,j,visited); } } } return new ArrayList<String>(set); } static String[] words2; // 方向，为了减少代码量 static int[][] direct = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; public void search(Tree root,int index, int i, int j, boolean[][] visited) { if(root.next[index] != null) { // 匹配到为true visited[i][j] = true; if(root.next[index].end) set.add(words2[root.next[index].index]); for(int[] arr : direct) { int x1 = i + arr[0]; int y1 = j + arr[1]; // 不约边，并且不重复浏览visited if(x1 >= 0 && x1 < x && y1 >= 0 && y1 < y && !visited[x1][y1]) { search(root.next[index],board2[x1][y1] - 'a',x1,y1,visited); } } // 处理完成变为false visited[i][j] = false; } } } class Tree { Tree[] next = new Tree[26]; boolean end = false; int index = 0; }