Interleaving String

97. Interleaving String

Using DFS

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        r, c = len(image), len(image[0])
        
        def dfs(ir, ic):
            cur_color = image[ir][ic]
            if cur_color != color:
                image[ir][ic] = color
            for jr, jc in ((ir-1, ic), (ir+1, ic), (ir, ic-1), (ir, ic+1)):
                if 0 <= jr < r and 0 <= jc < c and image[jr][jc] == cur_color and image[jr][jc] != color:
                    dfs(jr, jc)
        
        dfs(sr, sc)
        
        return image

Using a stack

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        nrows, ncols = len(image), len(image[0])
        
        stack = []
        stack.append((sr, sc))
        
        while stack:
            cur_r, cur_c = stack.pop()
            cur_color = image[cur_r][cur_c]
            if cur_color != color:
                image[cur_r][cur_c] = color
                for r, c in ((cur_r-1, cur_c), (cur_r+1, cur_c), (cur_r, cur_c-1), (cur_r, cur_c+1)):
                    if 0 <= r < nrows and 0 <= c < ncols and image[r][c] == cur_color:
                        stack.append((r, c))
                        
        return image