单词搜索_小米集团笔试题

我晕毛线

public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, word, visited, i, j, m, n, 0))
                   return true;
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int m, int n, int count){
        if(count == word.length()){
            return true;
        }
        if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(count))
            return false;
        if(visited[i][j])
            return false;
        visited[i][j] = true;
        boolean res = dfs(board, word, visited, i - 1, j, m, n, count + 1) || 
            dfs(board, word, visited, i + 1, j, m, n, count + 1) || 
            dfs(board, word, visited, i, j - 1, m, n, count + 1)||
            dfs(board, word, visited, i, j + 1, m, n, count + 1);
        visited[i][j] = false;
        return res;
    }
}

发表于 2017-08-04 12:49:31 回复(1)

勇敢牛牛，不怕困难！

class Solution {
public:
  bool exist(vector<vector<char>> &board, string word) {
    const int m = board.size(), n = board[0].size();
    for (int y = 0; y < m; ++y)
      for (int x = 0; x < n; ++x)
        if (search(board, word, m, n, x, y, 0))
          return true;
    
    return false;
  }
  
private:
  bool search(vector<vector<char>>& board, const string& word,
              const int m, const int n,
              int x, int y, int idx) {
    
    if (x < 0 || y < 0 || x == n || y == m || board[y][x] != word[idx])
      return false;
    
    if (idx == word.length() - 1)
      return true;
    
    const char t = board[y][x];
    board[y][x] = '#';
    bool found = search(board, word, m, n, x - 1, y, idx + 1)
              || search(board, word, m, n, x + 1, y, idx + 1)
              || search(board, word, m, n, x, y - 1, idx + 1)
              || search(board, word, m, n, x, y + 1, idx + 1);
 
    board[y][x] = t;
    return found;
  }
};

发表于 2021-07-11 13:20:50 回复(0)

promethus

// DFS应用
class Solution {
int direction[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int rows, cols;
vector<vector<bool>> visited;
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        if(rows == 0) return false;
        cols = board[0].size();
        int flag = false;
        visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
        for(int row = 0; row < board.size(); ++row)
        {
            for(int col = 0; col < board[row].size(); ++col)
            {
                flag = DFS(board, word, row, col, 0);
                if(flag == true)
                   return true;
            }
        }
        return false;
    }
    bool DFS(vector<vector<char>> &board, string &word, int row, int col, int index)
    {
        if(index == word.size() - 1)
            return board[row][col] == word[index];
        if(board[row][col] == word[index])
        {
            visited[row][col] = true;
            // 向四个方向搜索
            for(int i = 0; i < 4; ++i)
            {
                int x = row + direction[i][0];
                int y = col + direction[i][1];
                if(x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y])
                {
                    if(DFS(board, word, x, y, index + 1))
                        return true;
                }
            }
            //四个方向都没找到，回溯
            visited[row][col] = false;
        }
        return false;
    }
};

发表于 2019-08-13 20:54:57 回复(0)

顾翅

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(word.size()==0)
            return true;
        if(board.size()==0)
            return false;
        vector<vector<bool>>isVisited(board.size(),vector<bool>(board[0].size(),false));
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                if(board[i][j]==word[0]){
                    isVisited[i][j]=true;
                    if(dfs(board,i,j,word,0,isVisited))
                        return true;
                    isVisited[i][j]=false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> > &board,int i,int j,string word,int index,vector<vector<bool>>isVisited){
        if(index==word.size()-1&&board[i][j]==word[index])
            return true;
        if(board[i][j]!=word[index])
            return false;
        else{
            isVisited[i][j]=true;
            if(i+1<board.size()&&!isVisited[i+1][j]&&dfs(board,i+1,j,word,index+1,isVisited))
                return true;
            if(i-1>=0&&!isVisited[i-1][j]&&dfs(board,i-1,j,word,index+1,isVisited))
                return true;
            if(j+1<board[0].size()&&!isVisited[i][j+1]&&dfs(board,i,j+1,word,index+1,isVisited))
                return true;
            if(j-1>=0&&!isVisited[i][j-1]&&dfs(board,i,j-1,word,index+1,isVisited))
                return true;
        }
        return false;
    }
};

发表于 2018-06-22 22:16:58 回复(0)

C/C++

nbgao

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        int m = board.size();
        int n = board[0].size();
        for(int i=0;i<m;i++)
        	for(int j=0;j<n;j++)
        		if(DST(board,i,j,0,word))
        			return true;
        return false;
    }
    bool DST(vector<vector<char> > &board,int i,int j,int s,string word)
    {
    	int m = board.size();
    	int n = board[0].size();
    	if(word[s] == board[i][j])
    	{
    		if(s == word.size()-1)
    			return true;
    		char c = board[i][j];
    		board[i][j] = '*';
    		bool flag = (i+1<m && DST(board,i+1,j,s+1,word)) ||
    					(i>0 && DST(board,i-1,j,s+1,word)) ||
    					(j+1<n && DST(board,i,j+1,s+1,word)) ||
    					(j>0 && DST(board,i,j-1,s+1,word));
    		board[i][j] = c;
    		return flag;
		}
		return false;
	}
};

发表于 2017-09-13 00:47:38 回复(0)

ephonzhang

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (word.length() == 0) return true;
        boolean isExist = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    isExist |= existHelper(board, word, i, j);
                }
            }
        }
        return isExist;

    }

    public boolean existHelper(char[][] board, String word, int i, int j) {
        if (word.length() == 1 && board[i][j] == word.charAt(0)) return true;
        boolean isExist = false;
        if (board[i][j] == word.charAt(0)) {
            char[][] tempBoard = new char[board.length][board[0].length];
            for (int p = 0; p < board.length; p++) {
                tempBoard[p] = board[p].clone();
            }
            tempBoard[i][j] = '0';
            if (i > 0) isExist = isExist || existHelper(tempBoard, word.substring(1), i - 1, j);
            if (i < board.length - 1) isExist = isExist || existHelper(tempBoard, word.substring(1), i + 1, j);
            if (j > 0) isExist = isExist || existHelper(tempBoard, word.substring(1), i, j - 1);
            if (j < board[i].length - 1) isExist = isExist || existHelper(tempBoard, word.substring(1), i, j + 1);
        }
        return isExist;
    }
}

编辑于 2017-06-09 00:25:18 回复(0)

C/C++

xyxlil

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(search(board, i, j, 0, word))
                    return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board,int i, int j, int start, string word) {
        int m = board.size(), n = board[0].size();
        if(word[start] == board[i][j]) {
            if(start == word.size()-1)return true;
            char c = board[i][j];
            board[i][j] = '*';
            bool res =   (i+1<m && search(board, i+1,j,start+1,word))||
                    (j+1<n && search(board, i,j+1,start+1,word))||
                    (i-1>=0 && search(board, i-1,j,start+1,word))||
                    (j-1>=0 && search(board, i,j-1,start+1,word));
            board[i][j] = c;
            return res;
        }
        return false;
    }
};

发表于 2017-01-22 17:44:02 回复(0)

whisky_

//C++ DFS backtracking 的算法
class Solution {
public:
    bool isOut(int r, int c, int rows, int cols){
        return c<0 || c>=cols || r<0 || r>=rows;
    }
    bool DFS(vector<vector<char>> &board, int r, int c, string &word, int start){
        if(start>=word.size())
            return true;
        if(isOut(r, c, board.size(), board[0].size())||word[start]!=board[r][c])
            return false;
        
        int dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};
        char tmp=board[r][c];
        board[r][c]='.';
        for(int i=0; i<4; ++i){
            if(DFS(board, r+dx[i], c+dy[i], word, start+1))
               return true;
        }
        board[r][c]=tmp;
        return false;
    }
    bool exist(vector<vector<char> > &board, string word) {
        int rows=board.size(), cols=board[0].size();
        for(int r=0; r<rows; ++r)
            for(int c=0; c<cols; ++c){
                if(board[r][c]==word[0])
                    if(DFS(board, r, c, word, 0))
                        return true;
            }
        return false;
    }
};

发表于 2017-03-27 20:27:56 回复(4)

字节研发工程师

//人生中第一个自己做出来的DFS算法
public class Exist {
    public static int k=0;
    public static boolean exist(char[][] board, String word) {
        int m = board.length;
        System.out.println(m);
        int n = board[0].length;
        System.out.println(n);
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j <n ; j++) {
                if (dfs(board,i,j,word,k,visited))
                    return true;
            }
        return false;
    }

    private static boolean dfs(char[][] board, int i, int j, String word, int kth,boolean[][] visited) {
        if (kth>=word.length())
            return true;
        if (i>=0 && i<board.length && j>=0 && j<board[0].length && !visited[i][j] && word.charAt(kth)==board[i][j]){
            visited[i][j]=true;
            kth++;
            if (dfs(board,i,j+1,word,kth,visited) ||(dfs(board,i+1,j,word,kth,visited)||(dfs(board,i,j-1,word,kth,visited))||(dfs(board,i-1,j,word,kth,visited))))
                return true;
            visited[i][j] = false;//注意这里需要置为false
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        //char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "AAB";
        System.out.println(exist(board,word));
    }
}

发表于 2019-06-18 18:27:34 回复(0)

JacobGo！

/*
         * 应该是最优解法了吧。
	 * Runtime: 11 ms.Your runtime beats 80.21 % of java submissions.
	 * 该解法不需要建立对应的isVisited数组，来记录是否访问过某元素
	 * 用异或来进行标记
	 */
	public boolean exist(char[][] board, String word) {
		if (board == null || board.length == 0 || board[0].length == 0 || board == null)
			return false;
		char[] words = word.toCharArray();
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (solve(board, words, i, j, 0))
					return true;
			}
		}
		return false;
	}

	private boolean solve(char[][] board, char[] words, int i, int j, int index) {
		if (index >= words.length)
			return true;
		if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != words[index])
			return false;
		// 与512异或是防止递归中重复使用该元素。相当于一个标记(这里使用256,512,1024都可以)
		board[i][j] ^= 512;
		boolean flag = solve(board, words, i - 1, j, index + 1) 
				|| solve(board, words, i + 1, j, index + 1)
				|| solve(board, words, i, j - 1, index + 1) 
				|| solve(board, words, i, j + 1, index + 1);
		board[i][j] ^= 512;
		return flag;
	}

发表于 2017-06-30 12:26:23 回复(10)

页川先生

bool core(vector<vector<char>> &board,int i,int j,string word,int index,vector<vector<bool>> &isVisited){
        if(index==word.length())
            return true;
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||isVisited[i][j]||word[index]!=board[i][j])
            return false;
        bool res;
        isVisited[i][j]=true;
        res=core(board,i+1,j,word,index+1,isVisited)||
            core(board,i-1,j,word,index+1,isVisited)||
            core(board,i,j+1,word,index+1,isVisited)||
            core(board,i,j-1,word,index+1,isVisited);
        isVisited[i][j]=false;
        return res;
    }
    
    bool exist(vector<vector<char> > &board, string word) {
        vector<vector<bool>> isVisited(board.size(),vector<bool>(board[0].size(),false));
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(core(board,i,j,word,0,isVisited))
                    return true;
            }
        }
        return false;
    }

发表于 2017-11-06 14:46:22 回复(0)

STRUGGLExlf

import java.util.*;
public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null || board.length ==0 || board[0].length==0|| word==null || word.length()==0){
            return false;
        }
        int rows = board.length;
        int cols = board[0].length;

        for(int i=0; i<rows; i++){
            for(int j=0;j<cols;j++){
                if(dfs(board,word,0,i,j)){
                    return true;
                }
            }
        }
        return false; 
    }
    private boolean dfs(char[][] board, String word, int index, int row,int col){
        if(index==word.length()){
            return true;
        }
        int rows = board.length;
        int cols = board[0].length;
        if(row<0||row>=rows||col<0||col>=cols||board[row][col]!=word.charAt(index)){
            return false;
        }
        char temp = board[row][col];
        board[row][col]='#';

        boolean found = dfs(board,word,index+1,row-1,col)|| dfs(board,word,index+1,row+1,col)||dfs(board,word,index+1,row,col-1) || dfs(board,word,index+1,row,col+1);

        board[row][col] = temp;

        return found;
    }
}

发表于 2023-09-03 12:44:56 回复(0)

牛客515363438号

import java.util.*;
public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || word == null || word == ""){
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(this.dfs(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private static int[] dx = new int[]{-1,0,1,0};
    private static int[] dy = new int[]{0,-1,0,1};
    
    private boolean dfs(char[][] board, String word, int index, int x, int y){
        if(board[x][y] != word.charAt(index)){
            return false;
        }
        if(index == word.length() - 1){
            return true;
        }
        char temp = board[x][y];
        board[x][y] = '#';
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx<0 || nx >= board.length || ny < 0 
               || ny >= board[0].length || board[nx][ny] == '#'){
                continue;
            }
            if(this.dfs(board, word, index + 1, nx, ny)){
                return true;
            }
        }
        board[x][y] = temp;
        
        return false;
    }
}

发表于 2022-09-12 16:00:41 回复(0)

Nk_name

class Solution

{

public:

bool exist(vector<vector<char>>& board, string word)

{

rows = board.size(); // 计算行

cols = board[0].size(); // 计算列（矩阵可看做二维数组）

for(int i = 0; i < rows; i++) // 行遍历

{

for(int j = 0; j < cols; j++) // 列遍历

{

if(dfs(board, word, i, j, 0)) // 如果找到

{

return true;

}

// 遍历结束都没找到，返回false

return false;

}

private:

int rows, cols; // 行，列 i、j、k: 行索引，列索引，word中第k个字符

bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) // 深度优先搜索

{// 大于最后一行小于第一行列越界列越界未找到字符

if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) // 判断特殊情况

{

return false;

}

if(k == word.size() - 1)// 说明字符全部找到

{

return true;

}

// 递推：

board[i][j] = '\0'; // 先标记已被访问的值

// 按：下、上、右、左的顺序查找

// 使用或运算，代表只需找到一条可行路径就直接返回，不再做后续 DFS

bool res = dfs(board, word, i + 1, j, k + 1) // 下

|| dfs(board, word, i - 1, j, k + 1) // 上

|| dfs(board, word, i, j + 1, k + 1) // 右

|| dfs(board, word, i , j - 1, k + 1); // 左

board[i][j] = word[k]; // 还原当前矩阵元素

return res;

}

};

发表于 2022-05-04 17:04:25 回复(0)

她似星辰划过天边

// 直接暴力dfs
class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool dfs(vector<vector<char> > &board, int x, int y, string word, int state)
    {
        if(state >= word.size()) return true;
        
        char tmp = board[x][y];
        board[x][y] = '*';
        
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            
            if(a >= 0 && a < board.size() && b >= 0 && b < board[0].size() && board[a][b] == word[state])
            {
                if(dfs(board, a, b, word, state + 1))
                    return true;
            }
        }
        
        board[x][y] = tmp;
        return false;
    }
    
    bool exist(vector<vector<char> > &board, string word) {
        int n = board.size(), m = board[0].size();
        
        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, 1))
                        return true;
            }
        
        return false;
    }
};

编辑于 2022-02-09 18:18:38 回复(0)

牛客296074994号

//C++ DFS backtracking 的算法

classSolution {

public:

boolisOut(intr, intc, introws, intcols){

returnc<0 || c>=cols || r<0 || r>=rows;

}

boolDFS(vector<vector<char>> &board, intr, intc, string &word, intstart){

if(start>=word.size())

returntrue;

if(isOut(r, c, board.size(), board[0].size())||word[start]!=board[r][c])

returnfalse;

intdx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};

chartmp=board[r][c];

board[r][c]='.';

for(inti=0; i<4; ++i){

if(DFS(board, r+dx[i], c+dy[i], word, start+1))

returntrue;

}

board[r][c]=tmp;

returnfalse;

}

boolexist(vector<vector<char> > &board, string word) {

introws=board.size(), cols=board[0].size();

for(intr=0; r<rows; ++r)

for(intc=0; c<cols; ++c){

if(board[r][c]==word[0])

if(DFS(board, r, c, word, 0))

returntrue;

}

returnfalse;

}

发表于 2022-01-07 19:18:21 回复(0)

缓缓龟

class Solution {
public:
int X[4]={1,-1,0,0};
int Y[4]={0,0,1,-1};
bool dfs(int x,int y,int j,vector<vector<char>> board,string word,vector<vector<bool>>& vis){
vis[x][y]=1;
if(board[x][y]==word[j]){
j++;
if(j==word.size())
return true;
}
int x_,y_;
for(int i=0;i<4;i++){
x_ = x+X[i];
y_ = y+Y[i];
if(x_<0 || x_>=board.size() || y_<0 || y_>=board[0].size() || vis[x_][y_] || board[x_][y_]!=word[j])
continue;
bool res = dfs(x_,y_,j,board,word,vis);
if(res)
return true;
}
vis[x][y]=0;
return false;
}
bool exist(vector<vector<char> > &board, string word) {
vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),0));
for(int i=0;i<board.size();i++){
for(int j=0;j<board[i].size();j++)
if(board[i][j]==word[0])
if(dfs(i,j,0,board,word,vis))
return true;
}
return false;
}
};

发表于 2021-12-20 19:21:28 回复(0)

牛客114514810号

想知道究竟哪里超时了/(ㄒoㄒ)/~~
public class Solution {
    static boolean flag=false;
    static void dfs(char[][] table,boolean[][] flags,String current,String target,int i,int j){
        if(i>=0&&i<table.length&&j>=0&&j<table[0].length&&flags[i][j]==false){//out of index?
            current=current+table[i][j];
            flags[i][j]=true;
            if(current.equals(target)){
                flag=true;
                return;
            }
            dfs(table,flags,current,target,i+1,j);
            dfs(table,flags,current,target,i-1,j);
            dfs(table,flags,current,target,i,j+1);
            dfs(table,flags,current,target,i,j-1);
            flags[i][j]=false;
        }
        return ;
    }
    public boolean exist(char[][] table, String word) {
        flag=false;
        int N=table.length;
        int M=table[0].length;
        boolean[][] flags=new boolean[N][M];
        String cur="";
        for(int i=0;i<table.length;i++){
            for (int j=0;j<table[0].length;j++){
                if(table[i][j]==word.charAt(0));//第一个字符相同进入循环
                dfs(table,flags,cur,word,i,j);
            }
        }
        return flag;
    }
}

发表于 2021-09-26 17:50:00 回复(0)

牛客460903849号

/*简单的DFS操作，这边设置一个全局变量flag，

一旦找到目标值就设置为1，每次搜索先判断全局变量的flag的值，

减少遍历来剪枝，注意当无路可走时，将当前visit数组值复位。

**/
public class Solution {
    public static int flag = 0;
    public static int visit[][];

    public boolean exist(char[][] board, String word) {
        visit = new int[board.length][board[0].length];
        for (int i = 0; i < visit.length; i++)
            for (int j = 0; j < visit[i].length; j++)
                visit[i][j] = 0;
        loop: for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    search(board, i, j, visit, word, 0);
                    if (flag == 1)
                        break loop;
                }
            }
        if (flag == 1) {
            flag = 0;
            return true;
        } else
            return false;
    }

    public static void search(char[][] board, int x, int y, int visit[][], String word, int idx) {
        idx++;
        visit[x][y] = 1;
        if (idx >= word.length()) {
            flag = 1;
            return;
        }
  if (y + 1 < board[0].length && board[x][y + 1] == word.charAt(idx) && visit[x][y + 1] == 0 && flag !=1) {
            search(board, x, y + 1, visit, word, idx);
        }
     if (y - 1 >= 0 && board[x][y - 1] == word.charAt(idx) && visit[x][y - 1] == 0 && flag != 1) {
            search(board, x, y - 1, visit, word, idx);
        }
        if (x - 1 >= 0 && board[x - 1][y] == word.charAt(idx) && visit[x - 1][y] == 0 && flag != 1) {
            search(board, x - 1, y, visit, word, idx);
        }
        if (x + 1 < board.length && board[x + 1][y] == word.charAt(idx) && visit[x + 1][y] == 0 && flag != 1) {
            search(board, x + 1, y, visit, word, idx);
        }
        if (flag == 1)
            return;
        else
            visit[x][y] = 0;

    }

}

发表于 2021-09-10 11:41:28 回复(0)

爱看电影的小男孩

 public static boolean exist(char[][] board, String word) {
        //获取字符数组行数
        int n = board.length;
        //获取字符数组列数
        int m = board[0].length;
        //用来记录每次不同起点位置下 字符串已经遍历到的位置
        int k = 0;
        //设置一个二维布尔函数数组 默认都是false 如果已经遍历就设置为true
        boolean[][] bool = new boolean[n][m];
        //开始逐个进行遍历
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(DFS(board,i,j,k,word,bool))
                    return true;
            }
        }
        return false;
    }

    public static boolean DFS(char[][] board, int i, int j, int k, String word, boolean[][] bool) {
        //如果已经遍历完了word那么直接返回ture 表示已经包含
        if(k>=word.length()){
            return true;
        }
        /*
        判断当前的位置是否符合条件或者说是否在二维数组中，并且需要判断当前遍历的点是没有遍历过的即bool[i][j]当前位置为false
        判断当前字符是否和word中的第k个字符相等
         */
        if(i>=0 && i<board.length && j>=0 && j<board[0].length && word.charAt(k)==board[i][j] && !bool[i][j]){
            //开始寻找word的下一个字符
            k++;
            //并且将当前位置设置为true 反正等下迭代循环重复寻找
            bool[i][j]=true;
            //对当前点的四个点进行迭代
            if(DFS(board, i+1, j, k, word, bool)||DFS(board, i-1, j, k, word, bool)||DFS(board, i, j-1, k, word, bool)||DFS(board, i, j+1, k, word, bool))
                return true; //如果满足条件返回true
            //若当前点不满足条件 需要将他重新设置为false 标记为未读
            bool[i][j]=false;
        }
        //返回false
        return false;
    }

发表于 2021-09-04 21:06:03 回复(0)

单词搜索

问题信息

热门推荐

通过挑战的用户

相关试题