Java recursive solution.


  • 0
    C
    public boolean exist(char[][] board, String word) {
        boolean ret = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, int i, int j, int idx, String word) {
       if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || idx >= word.length() 
       || board[i][j] != word.charAt(idx)) {
           return false;
       }
       if (idx == word.length()-1) {
           return true;
       }
       char tmp = board[i][j];
       board[i][j] = '$';
       boolean ret = dfs(board, i-1, j, idx+1, word) || dfs(board, i+1, j, idx+1, word) ||
       dfs(board, i, j-1, idx+1, word) || dfs(board, i, j+1, idx+1, word);
       board[i][j] = tmp;
       return ret;
    }

Log in to reply
 

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