Can anybody help me to figure out why my solution takes double time than average?


  • 0
    S

    The idea is same as most posts'. I use recursive idea with a 2D array to record the status of each cell in board. It's accepted but it takes double time than average(800ms vs. 350ms). Can anyone help to figure out why? Thank you!

    public class Solution {
        public boolean exist(char[][] board, String word) {
            if (board == null || board.length == 0 || board[0].length == 0 || word == null || "".equals(word)) return false;
            for (int i = 0; i < board.length; i++)
                for (int j = 0; j < board[0].length; j++)
                    if(helper(i, j, new boolean[board.length][board[0].length], board, word, 0)) 
                        return true;
            return false;
        }
        
        public boolean helper(int row, int col, boolean[][] accessed, char[][] board, String word, int ind)
        {
            if (ind == word.length()) return true;
            if (board[row][col] != word.charAt(ind)) return false;
            accessed[row][col] = true;
            if (row != 0 && !accessed[row - 1][col] && helper(row - 1, col, accessed, board, word, ind + 1)) return true; 
            if (col != 0 && !accessed[row][col - 1] && helper(row, col - 1, accessed, board, word, ind + 1)) return true;
            if (row != board.length - 1 && !accessed[row + 1][col] && helper(row + 1, col, accessed, board, word, ind + 1)) return true;
            if (col != board[0].length - 1 && !accessed[row][col + 1] && helper(row, col + 1, accessed, board, word, ind + 1)) return true;
            if (ind == word.length() - 1) return true;
            accessed[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.