class Solution {
public boolean wordPuzzle(char[][] grid, String target) {
int m = grid.length;// 行数
int n = grid[0].length;// 列数
char[] words = target.toCharArray();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(grid, words, i, j, 0))
return true;
}
}
return false;
}
boolean dfs(char[][] grid, char[] words, int i, int j, int k) {
if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != words[k])
return false;
if (k == words.length - 1)
return true;
grid[i][j] = '\0';
boolean res = dfs(grid, words, i + 1, j, k + 1) || dfs(grid, words, i - 1, j, k + 1)
|| dfs(grid, words, i, j + 1, k + 1) || dfs(grid, words, i, j - 1, k + 1);
grid[i][j] = words[k];
return res;
}
}
class Solution {
public:
bool wordPuzzle(vector<vector<char>>& grid, string target) {
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> visit(m, vector<bool>(n, false));
for (int x = 0; x < m; x++) {
for(int y = 0; y < n; y++) {
if (recur(grid, visit, x, y, target, 0, m, n)) {
return true;
}
}
}
return false;
}
bool recur(vector<vector<char>>& grid, vector<vector<bool>>& visit, int x, int y, string target, int k, int m, int n) {
if(x >= m || y >= n || x < 0 || y < 0 || grid[x][y] != target[k] || visit[x][y] == true) {
return false;
}
if(k == target.size() - 1) {
return true;
}
visit[x][y] = true;
bool res = recur(grid, visit, x + 1, y, target, k + 1, m, n) || recur(grid, visit, x, y + 1, target, k + 1, m, n) ||
recur(grid, visit, x - 1, y, target, k + 1, m, n) || recur(grid, visit, x, y - 1, target, k + 1, m, n);
visit[x][y] = false;
return res;
}
};
public boolean wordPuzzle(char[][] board, String word) {
this.n = board.length;
this.m = board[0].length;
this.len = word.length();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
// DFS 搜索
boolean dfs(char[][] board, int i, int j, String word, int k) {
// 判断越界或字符不匹配
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)) {
return false;
}
// 如果已经到达最后一个字符
if (k == len - 1) {
return true;
}
// 临时标记为已访问
char temp = board[i][j];
board[i][j] = '\n'; // 标记当前字符为访问过
// 四个方向递归搜索
boolean res = dfs(board, i, j + 1, word, k + 1) ||
dfs(board, i + 1, j, word, k + 1) ||
dfs(board, i, j - 1, word, k + 1) ||
dfs(board, i - 1, j, word, k + 1);
// 恢复当前字符
board[i][j] = temp;
return res;
}
shuaidi
共以下 9 个回答
时间复杂度O(mn4^l)
空间复杂度O(l)
解题思路
– 1、把字符串分割成字符数组
– 2、把grid的每个位置作为起点去尝试匹配字符
– 如何匹配字符呢？按照上下左右的顺序去匹配
– 哪些表示匹配失败了呢？超过grid的上下限了 或者 匹配到已经匹配的单元格 或者 匹配上不相等
– 最终结束的标识？target的长度=已经匹配的长度
【题解1】
思路：回溯
回溯算法
class Solution {
public boolean wordPuzzle(char[][] grid, String target) {
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] target.charAt(0)){
if(dfs(grid, 0, target, i, j)){
return true;
}
}
}
}
return false;
}
}
时间：O（mn）
空间：O（mn）
回溯算法，用visit数组记录是否访问过。
时间复杂度O(M∗N)，空间复杂度O(M∗N)。
class Solution {
int n;
int m;
int len;
}
时间o(mn3叉树节点个数) 这个咋算？矩阵每个节点都遍历一遍树。
o（mn3^L）L是target的长度.
空间o(mn)
注意点：时间复杂度的计算。o（mn*3^L）L是target的长度。
除了第一次是4个方向外，之后都是3个方向，因为有来时路，valid=0。