Bomb Enemy

https://leetcode.com/problems/bomb-enemy/description/

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.

Note that you can only put the bomb at an empty cell.

Example:

For the given grid

0 E 0 0

E 0 W E

0 E 0 0

return 3. (Placing a bomb at (1,1) kills 3 enemies)

Thoughts

naive的方法是依次遍历, 每次遍历时lazy计算横竖各能炸多少个. 但可以观察到同一行前面的这行能炸的和当前点这行能炸的一样, 同理同一列前面访问过的能炸的和当前点能在该列炸掉的数是一样的. 因此我们可以用一个int变量rowCount记录当前点行能炸掉多少和一个数组colCount, colCount[j]记录当前点(i, j)在j列能炸掉多少. 当遇到新行/列或遇到新墙时, actively计算当前行和列能最炸掉多少并存入rowCount或colCount[j]里.

Code

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length;
        int n = m == 0 ? 0 : grid[0].length;
        int rowCount = 0;
        int[] colCount = new int[n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0 || grid[i][j - 1] == 'W') {
                    rowCount = 0;
                    for (int k = j; k < n && grid[i][k] != 'W'; k++) {
                        if (grid[i][k] == 'E') {
                            rowCount++;
                        }
                    }
                }
                if (i == 0 || grid[i - 1][j] == 'W') {
                    colCount[j] = 0;
                    for (int k = i; k < m && grid[k][j] != 'W'; k++) {
                        if (grid[k][j] == 'E') {
                            colCount[j]++;
                        }
                    }
                }

                if (grid[i][j] == '0') {
                    max = Math.max(max, rowCount + colCount[j]);
                }
            }
        }

        return max;
    }
}

Analysis

时间复杂度O(MN), 空间O(N).