【leetcode刷题笔记】Word Search
2024-08-29 18:55:47
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED"
, -> returns true
,
word = "SEE"
, -> returns true
,
word = "ABCB"
, -> returns false
.
题解:实现一个DFS函数 private boolean canFind(char[][] board,int i,int j,String left,boolean[][] visited) ,从(i,j)出开始搜索串left,visited数组记录某个位置是否包含在当前搜索的路径中,因为每个字符只能被使用一次。
代码如下:
public class Solution {
private boolean canFind(char[][] board,int i,int j,String left,boolean[][] visited){
//if we have found one path
if(left.equals(""))
return true; //look around point(i,j) see if we can find next char
char next = left.charAt(0);
if(i-1>=0 && !visited[i-1][j] && board[i-1][j]== next ){
visited[i-1][j] = true;
if(canFind(board, i-1, j, left.substring(1),visited))
return true;
visited[i-1][j]= false;
} if(j-1>=0 && !visited[i][j-1] && board[i][j-1]== next ){
visited[i][j-1] = true;
if(canFind(board, i, j-1, left.substring(1),visited))
return true;
visited[i][j-1]= false;
} if(i+1 < board.length && !visited[i+1][j] && board[i+1][j]== next ){
visited[i+1][j] = true;
if(canFind(board, i+1, j, left.substring(1),visited))
return true;
visited[i+1][j]= false;
} if(j+1 < board[0].length && !visited[i][j+1] && board[i][j+1]== next ){
visited[i][j+1] = true;
if(canFind(board, i, j+1, left.substring(1),visited))
return true;
visited[i][j+1]= false;
} return false;
}
public boolean exist(char[][] board, String word) {
if(word == null || word.length() == 0)
return true;
if(board.length == 0)
return false; int m = board.length;
int n = board[0].length;
char now = word.charAt(0);
boolean[][] visited = new boolean[m][n]; //search board for our first char in word
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j ++){
if(board[i][j]== now ){
visited[i][j]= true;
if(canFind(board, i, j, word.substring(1),visited))
return true;
visited[i][j]= false;
}
}
} return false;
}
}
最新文章
- 【BZOJ1662】[Usaco2006 Nov]Round Numbers 圆环数 数位DP
- HDOJ 2444 The Accomodation of Students
- 关于jquery中 跳出each循环的方法
- spider autohome (1)
- i++和++i的区别
- GitHub-更新数据
- c++迭代器(iterator)详解
- BestCoder Round #85 sum
- 关于全局变量和函数,在其他类中调用问题,extern关键字
- 【转】Android手机客户端关于二维码扫描的源码--不错
- grunt 的安装和简单使用
- C# 高性能 TCP 服务的多种实现方式
- HTML5_canvas_填充文本,描边文本
- 一步步学会用docker部署应用(nodejs版)
- LeetCode算法题-Longest Palindrome(五种解法)
- Java多线程(五)——线程等待与唤醒
- 24种java设计模式总结和目录
- Windows 动态链接库DLL使用
- 686. Repeated String Match
- Word 如何实现表格快速一分为二