Why my code runs so slow?


  • 0
    S

    I don't see much difference than the high votes solutions. But it runs really slow (more than 250ms). The average should be around 10ms, however. Please help me to point out what's wrong. Thank you in advance!!

    public class Solution {
        public boolean exist(char[][] board, String word) {
            if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
                return false;
            }
            
            for (int rowIndex = 0; rowIndex < board.length; rowIndex++) {
                for (int colIndex = 0; colIndex < board[0].length; colIndex++) {
                    if (dfsSearch(board, word, 0, rowIndex, colIndex, new boolean[board.length][board[0].length])) {
                        return true;
                    }
                }
            }
            return false;
            
        }
        
        private boolean dfsSearch(char[][] board, String word, int pos, int row, int col, boolean[][] used) {
            if (pos == word.length()) {
                return true;
            }
            
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || used[row][col]) {
                return false;
            }
            
            if (board[row][col] != word.charAt(pos)) {
                return false;
            }
            
            used[row][col] = true;
            if (   dfsSearch(board, word, pos + 1, row - 1, col, used) || dfsSearch(board, word, pos + 1, row + 1, col, used)
                || dfsSearch(board, word, pos + 1, row, col - 1, used) || dfsSearch(board, word, pos + 1, row, col + 1, used)) {
                return true;
            }
            used[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.