Why my Java DFS solution get TLE?


  • 0
    F

    It seems right,but get TLE

    public class Solution {
        
        private boolean[][] v;
        
        private boolean check(char[][] board, int si, int sj) {
            int row = board.length;
            int col = board[0].length;
            return (si >=0 && si < row && sj >=0 && sj < col);
        }
        
        private boolean search(char[][] board, int si, int sj, int idx, String word) {
            int row = board.length;
            int col = board[0].length;
            if (idx >= word.length() - 1) {
                return true;
            }
            int[] dx = new int[]{-1, 0, 1, 0};
            int[] dy = new int[]{0, -1, 0, 1};
            for (int i = 0; i < 4; i++) {
                    int ci = si + dx[i];
                    int cj = sj + dy[i];
                    if (check(board, ci, cj) && board[ci][cj] == word.charAt(idx + 1) && !v[ci][cj]) {
                        v[ci][cj] = true;
                        if(search(board, ci, cj, idx + 1, word)) {
                            return true;
                        }
                        v[ci][cj] = false;
                    }
            }
            return false;
        }
        
        public boolean exist(char[][] board, String word) {
            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;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    v = new boolean[row][col];
                    v[i][j] = true;
                    if (word.charAt(0) == board[i][j] && search(board, i, j, 0, word)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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