If Java o(mn * (logm+logn)) solution can be accepted, why so many python o(mn) solution can't?


  • 0
    W

    for example,
    this one: https://discuss.leetcode.com/topic/49077/too-strict-time-limit-on-python/11

    and in this link by @yixuebk : https://discuss.leetcode.com/topic/48566/short-o-mn-python/3

    It appears that the only option for python is to use its built-in function... like Stephan's answer.

    Interesting.


  • 0
    W

    I used split, join and count but made the code ugly...
    '''

    def maxKilledEnemies(self, grid):
    
        if (not grid) or (not grid[0]):
            return 0
    
        row = [[-1] for i in xrange(len(grid))]
        col = [[-1] for i in xrange(len(grid[0]))]
    
        rowenemy, colenemy = [], []
        for i in xrange(len(grid)):
            breakdown = ''.join(grid[i]).split('W')
            new = []
            for item in breakdown:
                new.append(item.count('E'))
            rowenemy.append(new)
    
        for j in xrange(len(grid[0])):
            breakdown = ''.join(grid[i][j] for i in xrange(len(grid))).split('W')
            new = []
            for item in breakdown:
                new.append(item.count('E'))
            colenemy.append(new)
    
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == 'W':
                    row[i].append(j)
                    col[j].append(i)
                if i == len(grid)-1:
                    col[j].append(len(grid))
            row[i].append(len(grid[0]))
    
        rowmap = [[0 for j in xrange(len(grid[0]))] for i in xrange(len(grid))]
        colmap = [[0 for j in xrange(len(grid))] for i in xrange(len(grid[0]))]
    
        for i in xrange(len(row)):
            for j in xrange(len(row[i])-1):
                for k in xrange(row[i][j]+1, row[i][j+1]):
                    rowmap[i][k] = rowenemy[i][j]
    
        for i in xrange(len(col)):
            for j in xrange(len(col[i])-1):
                for k in xrange(col[i][j]+1, col[i][j+1]):
                    colmap[i][k] = colenemy[i][j]
    
        ans = 0
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == '0' and rowmap[i][j]+colmap[j][i] > ans:
                    ans = rowmap[i][j]+colmap[j][i]
    
        return ans
    

    '''


Log in to reply
 

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