牛客NC242 单词搜索【中等递归DFS C++/Java/Go/PHP】

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2

思路

递归：以word第一个字符为起点，在矩阵中
递归搜索，检查是否存在完整的word路径，
注意恢复现场，又叫回溯，这是核心

参考答案C++

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param board string字符串vector* @param word string字符串* @return bool布尔型*/bool exist(vector<string>& board, string word) {//dfsint n = board.size();int m = board[0].size();vector<vector<bool>> visted(n, vector<bool>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (board[i][j] == word[0]) {if (dfs(board, i, j, word, 0, visted)) {return true;}}}}return false;}bool dfs(vector<string>& board, int i, int j, string word, int idx,vector<vector<bool>> visited) {if (idx == word.size())return true;if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||visited[i][j] || board[i][j] != word[idx])return false;visited[i][j] = true;//从上下左右搜索bool b1 = dfs(board, i - 1, j, word, idx + 1, visited);bool b2 = dfs(board, i + 1, j, word, idx + 1, visited);bool b3 = dfs(board, i, j - 1, word, idx + 1, visited);bool b4 = dfs(board, i, j + 1, word, idx + 1, visited);visited[i][j] = false; //恢复现场，又叫回溯return b1 || b2 || b3 || b4;}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param board string字符串一维数组* @param word string字符串* @return bool布尔型*/public boolean exist (String[] board, String word) {//dfsint n = board.length;int m = board[0].length();boolean[][] visited = new boolean[n][m];for (int i = 0; i < n ; i++) {for (int j = 0; j < m ; j++) {if (board[i].charAt(j) == word.charAt(0)) {//开始dfsif ( dfs(board, i, j, word, 0, visited)) {return true;}}}}return false;}//当前来到board的i行j列，检查board[i,j]是否等于word[idx]public boolean dfs(String[] board, int i, int j, String word, int idx,boolean[][] visited) {if (idx == word.length()) return true; //说明在矩阵中找到了单词//判断是否越界，是否访问过，检查board[i,j]是否等于word[idx]if (i < 0 || i >= board.length || j < 0 || j >= board[0].length() ||visited[i][j] || board[i].charAt(j) != word.charAt(idx)) {return false;}visited[i][j] = true;boolean b1 = dfs(board, i - 1, j, word, idx + 1, visited);boolean b2 =  dfs(board, i + 1, j, word, idx + 1, visited);boolean b3 =  dfs(board, i, j - 1, word, idx + 1, visited);boolean b4 =  dfs(board, i, j + 1, word, idx + 1, visited);visited[i][j] = false; //恢复现场，又叫回溯return b1 || b2 || b3 || b4;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param board string字符串一维数组* @param word string字符串* @return bool布尔型*/
func exist(board []string, word string) bool {//dfsn := len(board)m := len(board[0])visited := make([][]bool, n)for i := 0; i < n; i++ {visited[i] = make([]bool, m)}for i := 0; i < n; i++ {for j := 0; j < m; j++ {if board[i][j] == word[0] {if dfs(board, i, j, word, 0, visited) {return true}}}}return false
}func dfs(board []string, i, j int, word string, idx int, visited [][]bool) bool {if idx == len(word) {return true}if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[idx] {return false}visited[i][j] = true//上下左右搜索b1 := dfs(board, i-1, j, word, idx+1, visited)b2 := dfs(board, i+1, j, word, idx+1, visited)b3 := dfs(board, i, j-1, word, idx+1, visited)b4 := dfs(board, i, j+1, word, idx+1, visited)visited[i][j] = false //恢复现场，又叫回溯return b1 || b2 || b3 || b4
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param board string字符串一维数组 * @param word string字符串 * @return bool布尔型*/
function exist( $board ,  $word )
{//dfs$n= count($board);$m = strlen($board[0]);$visited =[];for($i=0;$i<$n;$i++){for($j=0;$j<$m;$j++){$visited[$i][$j]=false;}}for($i=0;$i<$n;$i++){for($j=0;$j<$m;$j++){if($board[$i][$j] ==$word[0]){if(dfs($board,$i,$j,$word,0,$visited)){return true;}}}}return false;
}function dfs($board,$i,$j,$word,$idx,$visited){if($idx == strlen($word))return true;if($i<0 || $i>=count($board) || $j<0 || $j>=strlen($board[0]) ||$visited[$i][$j] || $board[$i][$j]!=$word[$idx])return false;$visited[$i][$j]=true;//上下左右四个方向搜索$b1 = dfs($board,$i-1,$j,$word,$idx+1,$visited);$b2 = dfs($board,$i+1,$j,$word,$idx+1,$visited);$b3 = dfs($board,$i,$j-1,$word,$idx+1,$visited);$b4 = dfs($board,$i,$j+1,$word,$idx+1,$visited);$visited[$i][$j]=false; //恢复现场，又叫回溯return $b1||$b2||$b3||$b4;
}