Easy to understand JAVA solution


  • 4
    M
    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                }
                else {
                    if(i == 0 && j == 0) obstacleGrid[i][j] = 1;
                    else if(i == 0 && j > 0) obstacleGrid[i][j] = obstacleGrid[i][j-1];
                    else if(i > 0 && j == 0) obstacleGrid[i][j] = obstacleGrid[i-1][j];
                    else obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
        }
        return obstacleGrid[m-1][n-1];
    }
    }

  • 0
    Y

    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int[][] dpGrid = new int[obstacleGrid.length][obstacleGrid[0].length];
        for(int[] i : dpGrid)
        {
            Arrays.fill(i, -1);
        }
        if(obstacleGrid[obstacleGrid.length -1][obstacleGrid[0].length -1] == 1)
        {
            return 0;
        }
        return getAllPaths(obstacleGrid, dpGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1);
    }
    public int getAllPaths(int[][] grid,int[][] dpGrid, int m, int n)
    {
        if(m == 0 &&  n == 0)
        {
            if(grid[m][n] == 0)
            {
                return 1;
            }
            else
            {
                return 0;    
            }
            
        }
        else if(m < 0 || n < 0)
        {
            return 0;
        }else if(dpGrid[m][n] != -1)
        {
            return dpGrid[m][n];
        }
        else if(m == 0)
        {
            if(grid[m][n - 1] == 0)
            {
                dpGrid[m][n] = getAllPaths(grid, dpGrid, m, n - 1);
                return dpGrid[m][n];
                
            }else{
                dpGrid[m][n] = 0;
                return dpGrid[m][n];             
            }
        }
        else if(n == 0)
        {
            if(grid[m -1][n] == 0)
            {
                dpGrid[m][n] =getAllPaths(grid, dpGrid, m - 1, n); 
                return dpGrid[m][n];    
            }else{
                dpGrid[m][n] = 0;
                return dpGrid[m][n];
            }
            
        }
        else{
            if(grid[m - 1][n] == 0 && grid[m][n - 1] == 0)
            {
                dpGrid[m][n] = getAllPaths(grid,dpGrid, m -1, n) + getAllPaths(grid, dpGrid, m, n - 1);
                return (dpGrid[m][n]); 
            }else if(grid[m - 1][n] == 1 && grid[m][n - 1] == 0)
            {
                dpGrid[m][n] = getAllPaths(grid, dpGrid, m, n - 1);
                return 1 * (dpGrid[m][n]);
            }else if(grid[m - 1][n] == 0 && grid[m][n - 1] == 1)
            {
                dpGrid[m][n] = getAllPaths(grid, dpGrid, m -1 , n);
                return 1 * (dpGrid[m][n]);
            }
            else
            {
                dpGrid[m][n] = 0;
                return dpGrid[m][n];
            }
        }
    
    }
    

    }


Log in to reply
 

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