class Solution(object): def countBattleships(self, board): """ :type board: List[List[str]] :rtype: int """ cols = len(board) rows = len(board) ct = 0 for c in xrange(cols): for r in xrange(rows): # We count a battleship only first time we see it. If a battleship piece 'X' # is encountered, it is only new if neither the upper or left components are not also # pieces of the same battleship. These prior indices are guarenteed to already be explored by # the time we get to the current board index. if board[c][r] != 'X': continue if r > 0 and board[c][r - 1] == 'X': continue if c > 0 and board[c - 1][r] == 'X': continue ct += 1 return ct
Is it not still making n^2 calls or does the continue change that? (I've actually never used continue before)
@haxet my point is that u could say it was running at o(r * c) time or... if u set n = r * c, then you can say it's running at o(n) time. the continue statements don't impact that. they're just a slight optimization.
@vikram4 I mean I guess, but n is vague and you're saying that n increases linearly with time which is not right. It increases by the (#ofrows*#ofcols)
@haxet but it is linear to the number of grid spaces for a given situation, which is right. n is vague in this question, i will agree on that. but i don't see any reason to pick one interpretation over another.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.