博文中会简要介绍Leetcode P0079题目分析及解题思路。
“Word Search”是一道比较基础的深度优先搜索的问题，首先定位给定word在矩阵中的起点，每个起点深度优先搜索，直到搜索完所有定位，若存在则返回true，反之返回false
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.
以下是Java的题解代码实现。
class Solution {
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0)
return true;
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int r=0; r<m; ++r) {
for (int c=0; c<n; ++c) {
if (board[r][c] != word.charAt(0))
continue;
visited[r][c] = true;
if (this.search(board, word, visited, 1, r, c, m, n))
return true;
visited[r][c] = false;
}
}
return false;
}
private int[] dr = {0, 1, 0, -1};
private int[] dc = {1, 0, -1, 0};
private boolean search(char[][] board, String word, boolean[][] visited, int ptr, int row, int col, int m, int n) {
if (ptr >= word.length())
return true;
for (int di=0; di<4; ++di) {
int r = row+dr[di];
int c = col+dc[di];
// 若探索合法，且下次探索是指定的字符
if (r >= 0 && r < m
&& c >= 0 && c < n
&& !visited[r][c]
&& board[r][c] == word.charAt(ptr)) {
visited[r][c] = true;
if (this.search(board, word, visited, ptr+1, r, c, m, n)) {
visited[r][c] = false;
return true;
}
visited[r][c] = false;
}
}
return false;
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (word.size() == 0)
return true;
int m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int r=0; r<m; ++r) {
for (int c=0; c<n; ++c) {
if (board[r][c] != word[0])
continue;
visited[r][c] = true;
if (this->search(board, word, visited, 1, r, c, m, n))
return true;
visited[r][c] = false;
}
}
return false;
}
private:
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
bool search(vector<vector<char>> &board, string word, vector<vector<bool>> &visited, int ptr, int row, int col, int m, int n) {
if (ptr >= word.size())
return true;
for (int di=0; di<4; ++di) {
int r = row+dr[di];
int c = col+dc[di];
// 若探索合法，且下次探索是指定的字符
if (r >= 0 && r < m
&& c >= 0 && c < n
&& !visited[r][c]
&& board[r][c] == word[ptr]) {
visited[r][c] = true;
if (this->search(board, word, visited, ptr+1, r, c, m, n)) {
visited[r][c] = false;
return true;
}
visited[r][c] = false;
}
}
return false;
}
};