18 lines clear Python O(mn) solution


  • 0
    V

    I combined the two loops into a function. Now it looks much concise :)
    Please see the original post below if you need more explanation.

    class Solution(object):
        def maxKilledEnemies(self, grid):
            if not grid or not grid[0]: return 0
    
            def killed_rows(g):
                m, n = len(g), len(g[0])
                kills = [[0] * n for i in range(m)]
            
                for i in range(m):
                    s = count = 0
                    for j in range(n+1):
                        if j == n or g[i][j] == 'W':
                            for k in range(s, j):
                                if g[i][k] == '0':
                                    kills[i][k] = count
                            s = j + 1
                            count = 0
                        elif g[i][j] == 'E':
                            count += 1
                return kills
    
            hs, vs = killed_rows(grid), killed_rows(zip(*grid))
            return max(hs[i][j] + vs[j][i] for i in range(len(hs)) for j in range(len(hs[0])))
    

    Original Post:
    I scanned through the matrix two times to compute the number of horizontal and vertical kills respectively.

    The logic and shape of two loops are almost identical. So I think potentially we could write these two loops into one functions, and cut the code length quite a bit. Please let me know if you can think of a way to do it without losing readability :)

    class Solution(object):
        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid or not grid[0]: return 0
            m, n = len(grid), len(grid[0])
            kills = [[0] * n for i in range(m)]
    
            # Find num killed horizontally
            # For every row, scan through its columns
            # Initialize the count = 0, s = 0
            # if grid[i][j] == E: count += 1
            # if grid[i][j] == W:
            #   Update elements of kills
            for i in range(m):
                s = count = 0
                for j in range(n+1):
                    if j == n or grid[i][j] == 'W':
                        for k in range(s, j):
                            if grid[i][k] == '0':
                                kills[i][k] = count
                        s = j + 1
                        count = 0
                    elif grid[i][j] == 'E':
                        count += 1
    
            # Update num killed vertially
            for j in range(n):
                s = count = 0
                for i in range(m+1):
                    if i == m or grid[i][j] == 'W':
                        for k in range(s, i):
                            if grid[k][j] == '0':
                                kills[k][j] += count
                        s = i + 1
                        count = 0
                    elif grid[i][j] == 'E':
                        count += 1
            return max(max(row) for row in kills)
    

Log in to reply
 

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