CODEWITHSUNDEEP
pythonalgorithmdepth-first-search
gchandra
gchandra

Reputation: 94

Why does an implementation of an algorithmic problem not work?

The question is to find the number of islands. https://leetcode.com/problems/number-of-islands/

Solution 1:

class Solution:    
    def dfs(self, row, column, grid):
        if row < 0 or column < 0 or row>= len(grid) or column >= len(grid[0]):
            return 0
        if grid[row][column] == '0':
            return 0
        grid[row][column] = '0'                    
        self.dfs(row+1, column, grid)
        self.dfs(row-1, column, grid)
        self.dfs(row, column+1, grid)
        self.dfs(row, column-1, grid)
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                if grid[row][column] == '1':
                    self.dfs(row, column, grid)
                    count += 1

        return count

Solution 2(Doesn't work)

class Solution:
    def dfs(self, row, column, grid):
        if row < 0 or column < 0 or row>= len(grid) or column >= len(grid[0]):
            return 0
        if grid[row][column] == '0':
            return 0
        grid[row][column] = '0'                    
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i!=0 or j!=0:
                    self.dfs(row+i, column+j, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                if grid[row][column] == '1':
                    self.dfs(row, column, grid)
                    count += 1
        return count

Can anyone please explain why 2 doesn't work. I'm running a loop in which every statement gives a recursive call.

But this logic works in Java, why? https://www.youtube.com/watch?v=R4Nh-EgWjyQ

Upvotes: 0

Views: 461

Answers (1)

jlandercy
jlandercy

Reputation: 10992

The second code also consider diagonals as valid. This is why it differs from the first one. 

11000
11000
00100
00011

Both are valid codes but they do not answer the same question. The above input, first will return 1 and second 3.

Upvotes: 1

Related Questions