My DFS java solution


  • 0
    M

    public boolean exist(char[][] board, String word) {
    //DFS
    if(board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) return false;
    int row = board.length;
    int col = board[0].length;
    boolean[][] isVisited = new boolean[row][col];
    for(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
    if(!isVisited[i][j])
    if(dfs(board, word, isVisited, 0, i, j)) return true;
    }
    }
    return false;
    }
    public boolean dfs(char[][] board, String word, boolean[][] isVisited, int pos, int row, int col) {
    if(board[row][col] != word.charAt(pos)) return false;
    if(pos == word.length() - 1) {
    if(board[row][col] == word.charAt(pos)) return true;
    else return false;
    //return;
    }
    isVisited[row][col] = true;
    if(row>0 && !isVisited[row-1][col] && dfs(board, word, isVisited, pos+1, row-1, col)) return true;
    if(col<board[0].length-1 && !isVisited[row][col+1] && dfs(board, word, isVisited, pos+1, row, col+1)) return true;
    if(row<board.length-1 && !isVisited[row+1][col] && dfs(board, word, isVisited, pos+1, row+1, col)) return true;
    if(col>0 && !isVisited[row][col-1] && dfs(board, word, isVisited, pos+1, row, col-1)) return true;
    isVisited[row][col] = false;
    return false;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.