九号球普通 2023年11月30日下午9:27

“`java
class Solution {
int m;
int n;
boolean[][] visited;
public boolean wordPuzzle(char[][] grid, String target) {
if (grid == null || grid.length == 0) {
return false;
}
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { boolean flag = exists(grid, visited, i, j, target, 0); if (flag) { return true; } } } return false; }

public boolean exists(char[][] grid, boolean[][] visited, int i, int j, String target, int k) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target.charAt(k) || visited[i][j]) {
        return false;
    } else if (k == target.length() - 1){
        return true;
    }
    visited[i][j] = true;
    //上下左右去找
    boolean result = exists(grid, visited, i - 1, j, target, k + 1) || exists(grid, visited, i + 1, j, target, k + 1)
    || exists(grid, visited, i, j - 1, target, k + 1) || exists(grid, visited, i, j + 1, target, k + 1);
    visited[i][j] = false;
    return result;
}

}

0 赞同 0 条回复

Only You!(^-^(^-^)) 永久会员 2023年10月4日上午9:05

public class Solution {
    int m,n,len;
    public boolean exist(char[][] board, String word) {
        this.m = board.length;
        this.n = board[0].length;
        this.len = word.length();
        for (int i = 0;i < m;i++){
            for (int j = 0;j < n;j++){
                if (dfs(board,word,0,i,j)) return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int index,int i, int j){
        if (board[i][j] != word.charAt(index)){
            return false;
        }
        if (index == len - 1) return true;
        //直接利用board数组判断是否走过
        //能到这一步说明board[i][j] == word.charAt(index)，恢复时就这么恢复
        board[i][j] = '.';
        //  ||保证了前面为true后，后面不执行
        if(j + 1 < n){
            if (dfs(board, word, index +1, i, j + 1)) return true;
        }
        if (i + 1 < m){
            if (dfs(board, word, index +1, i + 1, j)) return true;
        }
        if (j - 1 >= 0){
            if (dfs(board, word, index +1, i, j - 1)) return true;
        }
        if (i - 1 >= 0){
            if (dfs(board, word, index +1, i - 1, j)) return true;
        }
        board[i][j] = word.charAt(index);
        return false;
    }
}

0 赞同 1 条回复

Only You!(^-^(^-^)) 永久会员 @ Only You!(^-^(^-^)) 2023年10月4日上午9:08

在递归过程提前判断i、j是否合法，可以减少每次进入递归时的需要判断的次数，略微加快速度；
用||的话也很精妙，前面为true了后面也不会执行了。

登录以回复

招舟子普通 2023年9月9日上午12:07

“`java
class Solution {
int m,n,len;
boolean[][] visited;
public boolean exist(char[][] board, String word) {
m = board.length;
n = board[0].length;
len = word.length();
visited = new boolean[m][n];
for(int i=0;i=m||j<0||j>=n||word.charAt(k)!=board[i][j]||visited[i][j]==true){
return false;
}
if(k==len-1){
return true;
}
visited[i][j]=true;
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));
visited[i][j]=false;
return res;
}
}
累

0 赞同 0 条回复

桀桀桀Jay 普通 2023年8月4日上午11:09

java
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();

        for(int i = 0; i < board.length; i++) {//i 表示行
            for(int j = 0; j < board[0].length; j++) { //j表示列

                if(dfs(board, words, i, j, 0)) { //寻找到首节点及后续节点
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        //剪枝判断有效，访问越界，元素不匹配，访问已经访问过的元素都无效
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || 
            board[i][j] != words[k]) {
                return false;
        }

        //终止条件, 已经访问到了最后一个元素，并且是有效的
        if(k == words.length - 1) {
            return true;
        }
        //记录已经访问过的元素，将它设为'\0' 后续的节点就不能往前走
        board[i][j] = '\0';
        //递归，判断上下左右的访问是否可行
        boolean res = dfs(board, words, i+1, j, k+1) ||  dfs(board, words, i-1, j, k+1)
            || dfs(board, words, i, j+1, k+1) || dfs(board, words, i, j-1, k+1);

        board[i][j] = words[k]; //这一方向不可行，回溯的时候需要重新到上一个节点

        return res;
    }
}

时间复杂度是O(3k次幂*MN), MN个起点，3的k次幂路径选择，空间复杂度是O(K), k次递归占用的空间

0 赞同 0 条回复

张开怀普通 2023年7月24日上午10:42

class Solution{
public:
       bool check(vector<char>& board,vector<vector<int>>& visited,int i, int j,string& s,int k){
              if(board[i][j]!=s[k]){
                     return false;
              }else if(k = s.length() -1){
                     return true;
              }
              visited[i][j] = true;
              vector<pair<int,int>> directions{{0,1},{0,-1},{1,0},{-1,0}};
              bool result = false;
              for(const auto& dir: directions){
                     int newi  = i+dir.first, newj = j+dir.second;
                     if(newi>=0 && newi< board.size() && newj>=0 && newj<board[0].size()){
                            if(!visited[newi][newj]){
                                   bool flag = check(board,visited,newi,newj,s,k+1);
                                   if(flag){
                                          result = true;
                                          break;
                                   }
                            }
                     }
              }
              visited[i][j] = false;
              return result;
       }
       bool exist(vector<vector<char>>& board,string word){
              int h = board.size(), w= board[0].size();
              vector<vector<int>> visited(h,vector<int>(w));
              for(int i=0; i<h; i++){
                     for(int j=0; j<w; j++){
                            bool flag = check(board, visited, i, j,word, 0);
                            if(flag){
                                   return true;
                            }
                     }
              }
              return false;
       }
};

时间复杂度：O(mn)
空间复杂度：：O(mn)

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:29

“`C++
bool backtrack(vector>& board, int row, int col, string& word, int index) {
// 如果已经找到了单词的末尾，说明匹配成功
if (index == word.size()) {
return true;
}
int m = board.size();
int n = board[0].size();
// 如果当前单元格的位置越界或字母不匹配，则返回 false
if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != word[index]) {
return false;
}

// 将当前单元格标记为已访问
char temp = board[row][col];
board[row][col] = '*';

// 在上、下、左、右四个方向上继续匹配下一个字母
bool result = backtrack(board, row - 1, col, word, index + 1) || 
              backtrack(board, row + 1, col, word, index + 1) ||
              backtrack(board, row, col - 1, word, index + 1) ||
              backtrack(board, row, col + 1, word, index + 1);

// 还原当前单元格，并返回结果
board[row][col] = temp;
return result;

}

bool exist(std::vector<std::vector>& board, std::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 (backtrack(board, i, j, word, 0)) {
            return true;
        }
    }
}

return false;

}

“`

0 赞同 0 条回复

BOZ 普通 2023年7月19日下午11:27

【思路】回溯，
【复杂度】时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    vector<vector<bool>> used;

    bool _exist(vector<vector<char>>& board, string &word, int i, int j, int k) {
        if (k >= word.size()) return true;
        char next = word[k];

        // up
        if (i != 0 && !used[i - 1][j] && board[i - 1][j] == next) {
            used[i - 1][j] = true;
            if (_exist(board, word, i - 1, j, k + 1)) return true;
            used[i - 1][j] = false;
        }

        // down
        if (i != board.size() - 1 && !used[i + 1][j] && board[i + 1][j] == next) {
            used[i + 1][j] = true;
            if (_exist(board, word, i + 1, j, k + 1)) return true;
            used[i + 1][j] = false;
        }

        // left
        if (j != 0 && !used[i][j - 1] && board[i][j - 1] == next) {
            used[i][j - 1] = true;
            if (_exist(board, word, i, j - 1, k + 1)) return true;
            used[i][j - 1] = false;
        }

        // right
        if (j != board[0].size() - 1 && !used[i][j + 1] && board[i][j + 1] == next) {
            used[i][j + 1] = true;
            if (_exist(board, word, i, j + 1, k + 1)) return true;
            used[i][j + 1] = false;
        }

        return false;
    }

public:

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();

        // initialize used matrix
        used.resize(m);
        for (auto &line: used) line.assign(n, false);

        // find the start charactor
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]){
                    used[i][j] = true;
                    if (_exist(board, word, i, j, 1)) return true;
                    used[i][j] = false;
                }
            }
        }

        return false;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月18日下午9:47

    int n;
    int m;
    int len;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.len = word.length();
        visited = new boolean[n][m];
        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;
    }
    boolean dfs(char[][] board, int i, int j, String word, int k) {
        if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        // 到达最后一个字符
        if(k == len - 1) {
            return true;
        }
        visited[i][j] = true;
        // 向右 下 左 上搜索
        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);
        // 回溯
        visited[i][j] = false;
        return res;
    }

0 赞同 0 条回复

局外人普通 2023年7月18日下午5:40

思路：回溯算法，DFS深度优先
时间复杂度O(mn) 空间复杂度O(mn)

class Solution {
    int count=0;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];

        dfs(0, 0, m, n, k);
        return count;
    }

    public void dfs(int row, int col, int m, int n, int k){
        if(row<0 || row>=m || col<0 || col>=n)  return;

        if(row/10 + row%10 + col/10 + col%10 > k)   return;

        if(visited[row][col])   return;

        count++;
        visited[row][col]=true;

        dfs(row, col+1, m, n, k);
        dfs(row+1, col, m, n, k);
        dfs(row, col-1, m, n, k);
        dfs(row-1, col, m, n, k);
    }

}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月17日上午5:58

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = [[0] * n for _ in range(m)]

        def backtrack(i, j, pos):
            if pos >= len(word):
                return True

            if i >= m or i < 0 or j >= n or j < 0 or word[pos] != board[i][j]:
                return False

            if visited[i][j] == 1:
                return False

            visited[i][j] = 1

            for dx, dy in directions:
                nx, ny = i + dx, j + dy
                if backtrack(nx, ny, pos + 1):
                    return True

            visited[i][j] = 0
            return False

        for i in range(m):
            for j in range(n):
                if backtrack(i, j, 0):
                    return True

        return False

检查是否符合以及是否重复走过

0 赞同 0 条回复

Vow the vow。普通 2023年7月16日下午12:03

典型的回溯法

int m,n;
    int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int index){
        if(board[i][j] != word.charAt(index) ) return false;
        if(index == word.length()-1){
            return true;
        }
        visited[i][j] = true;
        for(int[] d : directions){
            int x = i + d[0];
            int y = j + d[1];
            if(x < 0 || x >= m || y < 0 || y >=  n) continue;
            if(visited[x][y]) continue;
            if(dfs(board, word, x, y, index+1)) return true;
        }
        visited[i][j] = false;
        return false;
    }

0 赞同 0 条回复

Dsjh 普通 2023年7月16日上午10:44

MY

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    bool exist(vector<vector<char>>& board, string word) {
        int k=0;
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(dfs(board,word,i,j,k))
                    return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board,string word,int i,int j,int k){
        if(board[i][j] == ',')
            return false;
        if(board[i][j] != word[k])
            return false;
        // 用 size-1 判断成功， 用 size 可能最后一次进不来
        if(k == word.size()-1)
            return true;
        char c = board[i][j];
        board[i][j] = ',';
        for(int h=0;h<4;h++){
            int x = i+dir[h],y = j+dir[h+1];
            if(x>=0 && x<board.size() && y>=0 && y<board[0].size()){
                if(dfs(board,word,x,y,k+1))
                    return true;
            }
        }
        board[i][j] = c;
        return false;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月15日下午11:26

public boolean exist(char[][] board, String word){
        //遍历每一个位置，进行深搜
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, word, i, j, 0)){
                    return true;
                } 
            }
        }
        return false;
    }

    boolean dfs(char[][] board,String word,int i,int j,int len){

        //判断是否越界
        if(i < 0 || i >= board.length){
            return false;
        }
        if(j < 0 || j >= board[0].length){
            return false;
        }
        //判断是否符合
        if(board[i][j] != word.charAt(len)){
            return false;
        }

        //匹配完成
        if(len == word.length() - 1){
            return true;
        }

        //至此，表示当前位置匹配成功，且未匹配完成
        //设置已访问标志，继续向周围匹配
        board[i][j] = '\n';
        boolean res = dfs(board,word,i,j + 1,len + 1) ||
                    dfs(board,word,i + 1,j,len + 1) ||
                    dfs(board,word,i,j - 1,len + 1) ||
                    dfs(board,word,i - 1,j,len + 1);

        //回溯回来时，恢复访问标志位
        board[i][j] = word.charAt(len);

        return res;        

    }

0 赞同 0 条回复

Jerry 普通 2023年7月15日下午11:22

// DFS
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 找到就直接返回true
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        // 超过边界 或者 值不等
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) return false;
        // 表示字符找完了
        if (k == words.length - 1) return true;
        board[i][j] = '\0'; //标记找过的元素
        boolean result = dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1)
                || dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i, j - 1, k + 1);
        board[i][j] = words[k]; //还原找过的元素
        return result;
    }

}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Yodl. 普通 2023年7月15日下午5:41

//时间复杂度O(3^K*MN)
class Solution {
public:
    bool exist(vector>& 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;
            }
        }
        return false;
    }
private:
    int rows, cols;
    bool dfs(vector>& 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';//标记访问过的位置
        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;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月15日下午5:12

dfs+回溯

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

    private boolean dfs(int idx, int r, int c, boolean[][] check, char[][] board, String word) {
        if (idx == word.length()) {
            return true;
        }
        char next = word.charAt(idx);
        check[r][c] = true;
        if (r > 0 && !check[r-1][c] && board[r-1][c] == next && dfs(idx+1, r-1, c, check, board, word)) {
            return true;
        }
        if (r < board.length-1 && !check[r+1][c] && board[r+1][c] == next && dfs(idx+1, r+1, c, check, board, word)) {
            return true;
        }
        if (c > 0 && !check[r][c-1] && board[r][c-1] == next && dfs(idx+1, r, c-1, check, board, word)) {
            return true;
        }
        if (c < board[r].length-1 && !check[r][c+1] && board[r][c+1] == next && dfs(idx+1, r, c+1, check, board, word)) {
            return true;
        }
        check[r][c] = false;
        return false;
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月15日下午3:06

时间复杂度O(3^K*MN)

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

class Solution {
    bool dfs(vector<vector<char>>& board, string& word, int startIndex, int x, int y)
    {
        if(startIndex>=word.size())
            return true;
        for(int i=0;i<4;i++)
        {
            int a = x+dx[i];
            int b = y+dy[i];
            if(a>=0&&a<board.size()&&b>=0&&b<board[0].size()&&board[a][b]!='#')
            {
                if(board[a][b]==word[startIndex])
                {
                    // cout<<a<<" "<<b<<" "<<board[a][b]<<endl;
                    char tmp = board[a][b];
                    board[a][b]='#';
                    if(dfs(board, word, startIndex+1, a, b))
                        return true;
                    board[a][b]=tmp;
                }

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

0 赞同 0 条回复

【回溯专题】剑指 Offer 12. 矩阵中的路径

共以下 17 个回答

MY

# 回答此问题取消回复

【回溯专题】剑指 Offer 12. 矩阵中的路径

共以下 17 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复