leetcode算法-单词搜索-79

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

leetcode算法-单词搜索

leetcode传送门

题目

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

解题思路

本题的实质是寻找一条网格中的无重复路径,使得该路径上的字符连起来等于指定字符串。
一个基本的思路是遍历该网格,寻找第一个与字符串首字符一致的元素,然后以该元素为基准,从上下左右各个方向进行深度优先遍历,如果寻找到一条路径上的元素等于该字符串就可以直接返回true,如果没有找到,则继续遍历寻找。
需要注意的是路径不能重复,因此我使用了一个和网格大小一致的boolean数组来表示网格上某点是否已经访问过,从而保证无重复。
找到某个网格点对应的字符等于字符串首字符之后,我们可以使用回溯算法来进行后续的深度优先遍历。如果到目前为止访问过的元素多和字符串一致,则继续遍历,不一致则换别的方向继续进行深度优先遍历，如果所有方向都遍历之后都没有找到合适的路径,则寻找下一个网格点和单词首字符一致的网格点。

代码

class Solution {public boolean exist(char[][] board, String word) {if (board == null || "".equals(word) || board.length == 0 || board[0].length == 0)return false;//网格的访问映射boolean isVisited[][] = new boolean[board.length][board[0].length];char[] chs = word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (chs[0] == board[i][j]) {if (find(board, i, j, isVisited, chs, 0)) {return true;}}}}return false;}//对网格点进行深度优先遍历public static boolean find(char[][] board, int i, int j, boolean isVisited[][], char chs[], int index) {if (!isVisited[i][j] && chs[index] == board[i][j]) {int lenRow = board.length, lenCol = board[0].length;isVisited[i][j] = true;if (index == chs.length - 1) {return true;}if (j>0&&find(board, i, j - 1, isVisited, chs, index + 1)) {//左return true;}if (j<lenCol-1&&find(board, i, j + 1, isVisited, chs, index + 1)) {//右return true;}if (i>0&&find(board, i - 1, j, isVisited, chs, index + 1)) {//上return true;}if (i<lenRow-1&&find(board, i + 1, j, isVisited, chs, index + 1)) {//下return true;}isVisited[i][j] = false;}return false;}
}