My DFS java solution


  • 0
    E
    public class Solution {
        public boolean exist(char[][] board, String word) {
            // sanity check
            if (board == null || board.length == 0) {
                return false;
            }
            if (word == null || word.length() == 0) {
                return true;
            }
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (DFS(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
            return false;
        }
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        private boolean DFS(char[][] board, int x, int y, String word, int index) {
            // base case
            if (index == word.length()) {
                return true;
            }
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == '#') {
                return false;
            }
            // recursive rule
            if (word.charAt(index) == board[x][y]) {
                char tmp = board[x][y];
                board[x][y] = '#';
                for (int i = 0; i < 4; i++) {
                    if (DFS(board, x + dx[i], y + dy[i], word, index + 1)) {
                        return true;
                    }
                }
                board[x][y] = tmp;
            }
            return false;
        }
    }
    

Log in to reply
 

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