Python iterative/recursive BFS/DFS


  • 2
    Z

    I first used a "visited" set to store visited point, and then I found my old implementation set the visited point to "2", as posted. Then I was confused, isn't string immutable?

    Problem solved: input are not list of strings.

    def numIslands(self, grid):
        # BFS
        if not grid:
            return 0
        m, n, count = len(grid), len(grid[0]), 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1
                    stack = [(i,j)]
                    for ii,jj in stack:
                        if 0<=ii<m and 0<=jj<n and grid[ii][jj] == "1":
                            grid[ii][jj] = "2"
                            stack.extend([(ii+1,jj),(ii-1,jj),(ii,jj-1),(ii,jj+1)])
        return count
    
        # DFS
        if not grid:
            return 0
        m, n, count = len(grid), len(grid[0]), 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1
                    stack = [(i,j)]
                    while stack:
                        ii, jj = stack.pop()
                        if 0<=ii<m and 0<=jj<n and grid[ii][jj] == "1":
                            grid[ii][jj] = "2"
                            stack.extend([(ii+1,jj),(ii-1,jj),(ii,jj-1),(ii,jj+1)])
        return count
    
        ## recursive DFS
        def dfs(grid, i,j):
            if 0<=i<m and 0<=j<n and grid[i][j] == "1":
                grid[i][j] = "2"
                dfs(grid, i-1, j)
                dfs(grid, i+1, j)
                dfs(grid, i, j-1)
                dfs(grid, i, j+1)
        if not grid:
            return 0
        m, n, count = len(grid), len(grid[0]), 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1
                    dfs(grid, i, j)
        return count

  • 0

    Yes, Python strings are immutable.


  • 0
    Z

    Hey Stefan! Then why in this problem we are able to reset the string value?


  • 0

    I guess you think the input is a list of strings? It's not. Print the grid to see what you actually get or check the signature specification and you'll see it's a list of lists of (single-character) strings.


  • 0
    Z

    I see. Thank you for the answer! I updated the post.


Log in to reply
 

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