36ms JAVA O(mn) solution....


  • 0
    D
    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            int height = grid.length;
            if (height==0) return 0;
            int width = grid[0].length;
            if (width==0) return 0;
            
            int max=  0;
            int[] colKilled = new int[width];
            for (int j=0; j<width; j++) colKilled[j] = getKilledInColumn(grid,height,0,j);
            for (int i=0; i<height; i++) {
                int rowKilled = getKilledInRow(grid,width,i,0);
                for(int j=0; j<width; j++) {
                    if (grid[i][j]=='W') {
                        if (i+1<height) colKilled[j] = getKilledInColumn(grid,height,i+1,j);
                        if (j+1<width) rowKilled = getKilledInRow(grid,width,i,j+1);
                    } else if (grid[i][j]=='0'){
                        max = Math.max(max, rowKilled+colKilled[j]);
                    }
                }
            }
            return max;
        }
        private int getKilledInRow(char[][] grid, int width, int i, int j) {
            int count = 0;
            while(j<width && grid[i][j]!='W') if(grid[i][j++]=='E') count++;
            return count;
        }
        private int getKilledInColumn(char[][] grid, int height, int i, int j) {
            int count = 0;
            while(i<height && grid[i][j]!='W') if(grid[i++][j]=='E') count++;
            return count;
        }
    }
    

Log in to reply
 

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