NC242. 单词搜索
描述
示例1
输入:
["XYZE","SFZS","XDEE"],"XYZZED"
输出:
true
示例2
输入:
["XYZE","SFZS","XDEE"],"SEE"
输出:
true
示例3
输入:
["XYZE","SFZS","XDEE"],"XYZY"
输出:
false
C++ 解法, 执行用时: 5ms, 内存消耗: 428KB, 提交时间: 2022-02-11
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board string字符串vector
* @param word string字符串
* @return bool布尔型
*/
vector<string> buff;
bool exist(vector<string>& board, string word)
{
int wLen = word.size();
int rLen = board.size();
int cLen = board[0].size();
buff = board;
for (int r = 0; r < rLen; ++r)
{
for (int c = 0; c < cLen; ++c)
{
if (Find(board, word, 0, r, c, rLen, cLen))
{
return true;
}
}
}
return false;
}
bool Find(vector<string>& board, string & word, int index, int r, int c, int& rLen, int& cLen)
{
if (index == word.size()) return true;
bool res = false;
if (r >= 0 && r < rLen && c >= 0 && c < cLen && board[r][c] == word[index])
{
board[r][c] = 0;
++index;
res = Find(board, word, index, r + 1, c, rLen, cLen);
res = res || Find(board, word, index, r - 1, c, rLen, cLen);
res = res || Find(board, word, index, r, c + 1, rLen, cLen);
res = res || Find(board, word, index, r, c - 1, rLen, cLen);
board[r][c] = buff[r][c];
}
return res;
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 444KB, 提交时间: 2022-07-20
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board string字符串vector
* @param word string字符串
* @return bool布尔型
*/
bool exist(vector<string>& board, string word) {
m =board.size(),n=board[0].size(),k=word.size();
memset(st,false,sizeof st);
//memset(d,false,sizeof d);
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
{
st[i][j]=true;
if(dfs(i,j,0,board,word)) return true;
st[i][j]=false;
}
//dfs(0,0,0,board,word);
return false;
}
int m,n,k;
//bool d[100][100][1000];
bool st[100][100];
int mx[4]={1,0,-1,0},my[4]={0,1,0,-1};
bool dfs(int x,int y,int l ,vector<string>& b,string& w)
{
if(b[x][y]!=w[l]) return false;
//if(d[x][y][l]) return false;
//cout<<x<<" "<<y<<" "<<l<<endl;
if(l==k-1) return true;
bool res=false;
for(int i=0;i<4;++i)
{
int newx = x+mx[i],newy= y+my[i];
if(newx>=0 && newx<m && newy>=0 && newy<n && !st[newx][newy])
{
//cout<<" newx:"<<newx<<" newy:"<<newy<<endl;
st[newx][newy]=true;
res |= dfs(newx,newy,l+1,b,w);
st[newx][newy]=false;
if(res) return true;
}
}
//d[x][y][l] = res;
return res;
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 448KB, 提交时间: 2021-12-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board string字符串vector
* @param word string字符串
* @return bool布尔型
*/
bool exist(vector<string>& board, string word) {
int rows=board.size();
int cols=board[0].size();
used.resize(rows, vector<int>(cols, 0));
for(int i=0;i<rows;++i) {
for(int j=0;j<cols;++j) {
if(serch(board, i, j, word.c_str())) {
return true;
}
}
}
return false;
}
private:
const int px[4]={-1,0,1,0};
const int py[4]={0,1,0,-1};
vector<vector<int>> used;
bool serch(vector<string>& board, int x, int y, const char *str) {
char ch=*str;
if(ch==0) return true;
if(board[x][y]!=ch) return false;
if(*(++str)==0) return true;
int rows=board.size();
int cols=board[0].size();
used[x][y]=1;
for(int i=0;i<4;++i) {
int newx=x+px[i];
int newy=y+py[i];
if(newx>=0 && newx<rows && newy>=0 && newy<cols && used[newx][newy]==0) {
if(serch(board, newx, newy, str)) {
return true;
}
}
}
used[x][y]=0;
return false;
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 512KB, 提交时间: 2022-01-26
class Solution1 {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board string字符串vector
* @param word string字符串
* @return bool布尔型
*/
bool exist(vector<string>& board, string word)
{
int col = board[0].length();
int row = board.size();
vector<bool> vec(col, false);
vector<vector<bool>> isVisited(row, vec);
pair<int, int> p(0,0);
vector<pair<int, int>> loc(4, p);
for(int i=0; i < row; ++i)
for(int j=0; j < col; ++j)
{
int wordIdx = 0;
dfs(board, word, isVisited, wordIdx, i, j, loc);
if(wordIdx == word.length())
return true;
}
return false;
}
void dfs(vector<string> &board, string word, vector<vector<bool>> &isVisited, int &wordIdx, int row, int col, vector<pair<int, int>> loc)
{
if(board[row][col] == word[wordIdx] && isVisited[row][col] == false)
{
isVisited[row][col] = true;
if(++wordIdx == word.length())
return;
loc[0].first=row-1, loc[0].second = col;
loc[1].first=row+1, loc[1].second = col;
loc[2].first=row, loc[2].second = col-1;
loc[3].first=row, loc[3].second = col+1;
int curCnt = wordIdx;
for(int k = 0; k<loc.size(); ++k)
{
if(loc[k].first >=0 && loc[k].first < board.size() &&
loc[k].second >=0 && loc[k].second < board[0].length())
{
dfs(board, word, isVisited, wordIdx, loc[k].first, loc[k].second, loc);
if(wordIdx == word.length())
return;
}
}
if(curCnt == wordIdx)
--wordIdx;
isVisited[row][col] = false;
}
}
};
class Solution
{
public:
bool exist(vector<string> &board,string word)
{
int rows=board.size();
int cols=board[0].size();
used.resize(rows,vector<int>(cols,0));
for(int i=0;i<rows;++i)
{
for(int j=0;j<cols;++j)
{
if(serch(board,i,j,word.c_str()))
{
return true;
}
}
}
return false;
}
private:
const int px[4]={-1,0,1,0};
const int py[4]={0,1,0,-1};
vector<vector<int>> used;
bool serch(vector<string> &board,int x,int y,const char *str)
{
char ch=*str;
if(ch==0)
return true;
if(board[x][y]!=ch)
return false;
if(*(++str)==0)
return true;
int rows=board.size();
int cols=board[0].size();
used[x][y]=1;
for(int i=0;i<4;++i)
{
int newx=x+px[i];
int newy=y+py[i];
if(newx>=0&&newx<rows&&newy>=0&&newy<cols&&used[newx][newy]==0)
{
if(serch(board,newx,newy,str))
{
return true;
}
}
}
used[x][y]=0;
return false;
}
};
C 解法, 执行用时: 5ms, 内存消耗: 524KB, 提交时间: 2022-06-07
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board string字符串一维数组
* @param boardLen int board数组长度
* @param word string字符串
* @return bool布尔型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdbool.h>
void existRecursive(char** board, int x, int y, int rowLen, int colLen, int **visited, char *word, int wordLen, int k, bool *existWord) {
if (k == wordLen) {
*existWord = true;
return;
}
visited[x][y] = 1;
if (x > 0 && visited[x-1][y] == 0 && board[x-1][y] == word[k]) {
existRecursive(board, x-1, y, rowLen, colLen, visited, word, wordLen, k+1, existWord);
if (*existWord) {
return;
}
}
if (y > 0 && visited[x][y-1] == 0 && board[x][y-1] == word[k]) {
existRecursive(board, x, y-1, rowLen, colLen, visited, word, wordLen, k+1, existWord);
if (*existWord) {
return;
}
}
if (x < rowLen - 1 && visited[x+1][y] == 0 && board[x+1][y] == word[k]) {
existRecursive(board, x+1, y, rowLen, colLen, visited, word, wordLen, k+1, existWord);
if (*existWord) {
return;
}
}
if (y < colLen - 1 && visited[x][y+1] == 0 && board[x][y+1] == word[k]) {
existRecursive(board, x, y+1, rowLen, colLen, visited, word, wordLen, k+1, existWord);
if (*existWord) {
return;
}
}
visited[x][y] = 0;
}
bool exist(char** board, int boardLen, char* word ) {
int wordLen = strlen(word);
if (wordLen == 0) {
return true;
} else if (boardLen == 0 || board == NULL) {
return false;
}
bool existWord = false;
int rowLen = boardLen, colLen = strlen(board[0]);
int **visited = (int **)malloc(sizeof(int *) * boardLen);
for (int i = 0; i < boardLen; i++) {
visited[i] = (int *)malloc(sizeof(int) * colLen);
memset(visited[i], 0, sizeof(int) * colLen);
}
for (int i = 0; i < boardLen; i++) {
for (int j = 0; j < colLen; j++) {
if (board[i][j] == word[0]) {
existRecursive(board, i, j, boardLen, colLen, visited, word, wordLen, 1, &existWord);
if (existWord) {
return true;
}
}
}
}
return existWord;
}