DP + DFS, but get TLE problem, help improve my algorithm


  • 1
    K

    I use the DFS search for each char in the char array and add dynamic programming method to decrease the program times. But I still get the time limit errors when passing test cases. Who can help me improve my algorithm? Very thanks!

    public class Solution {
    
    public char[][] dp;
    public int xlimit;
    public int ylimit;
    
    public ArrayList<Integer> dfs;
    
    public char search(char[][] board, int index_x, int index_y){
        
        
        int number = index_x * ylimit + index_y;
        dfs.add(number);
        
        if(dp[index_x][index_y] != 'N'){
            return dp[index_x][index_y];
        }
        
        if(index_x == 0 || index_x == xlimit - 1){
            dp[index_x][index_y] = board[index_x][index_y];
            return board[index_x][index_y];
        }
        if(index_y == 0 || index_y == ylimit - 1){
            dp[index_x][index_y] = board[index_x][index_y];
            return board[index_x][index_y];
        }
        else{
            int number1 = (index_x - 1) * ylimit + index_y;
            if(!dfs.contains(number1)){
                if(dp[index_x-1][index_y] == 'O')
                    return 'O';
                if(search(board, index_x - 1, index_y) == 'O'){
                    dp[index_x][index_y] = 'O';
                    return 'O';
                }
            }
            
            int number2 = (index_x + 1) * ylimit + index_y;
            if(!dfs.contains(number2)){
                if(dp[index_x+1][index_y] == 'O')
                    return 'O';
                if(search(board, index_x + 1, index_y) == 'O'){
                    dp[index_x][index_y] = 'O';
                    return 'O';
                }
            }
            
            int number3 = index_x * ylimit  + index_y - 1;
            if(!dfs.contains(number3)){
                if(dp[index_x][index_y - 1] == 'O')
                    return 'O';
                if(search(board, index_x, index_y - 1) == 'O'){
                    dp[index_x][index_y] = 'O';
                    return 'O';
                }
            }
            
            int number4 = index_x * ylimit  + index_y + 1;
            if(!dfs.contains(number4)){
                if(dp[index_x][index_y + 1] == 'O')
                    return 'O';
                if(search(board, index_x, index_y + 1) == 'O'){
                    dp[index_x][index_y] = 'O';
                    return 'O';
                }
            }
            dp[index_x][index_y] = 'X';
            return 'X';
        }
    }
    
    public void solve(char[][] board) {
        
        if(board.length == 0 || board.length == 1)
            return;
        if(board[0].length == 1)
            return; 
        
        xlimit = board.length;
        ylimit = board[0].length;
        dp = new char[xlimit][ylimit];
        
        
        for(int i=0; i<xlimit; i++){
            for(int j=0; j<ylimit; j++){
                if(board[i][j] == 'X')
                    dp[i][j] = 'X';
                else
                    dp[i][j] = 'N';
            }
        }
        
        for(int i=0; i<xlimit; i++){
            for(int j=0; j<ylimit; j++){
                
                if(board[i][j] == 'O'){
                    
                    if(dp[i][j] == 'X')
                        board[i][j] = 'X';
                    else if(dp[i][j] == 'N'){
                        dfs = new ArrayList<Integer>();
                        board[i][j] = search(board, i, j);
                    }
                }
                else
                    continue;
                    
            }
        }
        
        return; 
    }
    

    }


Log in to reply
 

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