Easy Understand java dp solution!


  • 0
    W

    I use four dp matrix to store the enemies from the four directions. Time complexity and space complexity are both O(mn)

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            int length1=grid.length;
            if(length1==0){
                return 0;
            }
            int length2=grid[0].length;
            int[][] dp1=new int[length1][length2];
            int[][] dp2=new int[length1][length2];
            for(int i=0;i<length1;i++){
                for(int j=0;j<length2;j++){
                    if(grid[i][j]=='0'){
                        if(j>0){
                            dp1[i][j]=dp1[i][j-1];
                        }else{
                            dp1[i][j]=0;
                        }
                        if(i>0){
                            dp2[i][j]=dp2[i-1][j];
                        }else{
                            dp2[i][j]=0;
                        }
                    }else if(grid[i][j]=='E'){
                        if(j>0){
                            dp1[i][j]=dp1[i][j-1]+1;
                        }else{
                            dp1[i][j]=1;
                        }
                        if(i>0){
                            dp2[i][j]=dp2[i-1][j]+1;
                        }else{
                            dp2[i][j]=1;
                        }
                    }else{
                        dp1[i][j]=0;
                        dp2[i][j]=0;
                    }
                }
            }
            int[][] dp3=new int[length1][length2];
            int[][] dp4=new int[length1][length2];
            for(int i=length1-1;i>=0;i--){
                for(int j=length2-1;j>=0;j--){
                    if(grid[i][j]=='0'){
                        if(j<length2-1){
                            dp3[i][j]=dp3[i][j+1];
                        }else{
                            dp3[i][j]=0;
                        }
                        if(i<length1-1){
                            dp4[i][j]=dp4[i+1][j];
                        }else{
                            dp4[i][j]=0;
                        }
                    }else if(grid[i][j]=='E'){
                        if(j<length2-1){
                            dp3[i][j]=dp3[i][j+1]+1;
                        }else{
                            dp3[i][j]=1;
                        }
                        if(i<length1-1){
                            dp4[i][j]=dp4[i+1][j]+1;
                        }else{
                            dp4[i][j]=1;
                        }
                    }else{
                        dp3[i][j]=0;
                        dp4[i][j]=0;
                    }
                }
            }
            int max=0;
            for(int i=0;i<length1;i++){
                for(int j=0;j<length2;j++){
                    if(grid[i][j]=='0'){
                        int sum=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j];
                        if(sum>max)
                        max=sum;
                    }
                }
            }
            return max;
        }
    }

Log in to reply
 

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