Problem description:

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

https://assets.leetcode.com/uploads/2020/07/15/1.png

1
2
3
Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation:There are two valid cycles shown in different colors in the image below:

https://assets.leetcode.com/uploads/2020/07/15/11.png

Example 2:

https://assets.leetcode.com/uploads/2020/07/15/22.png

1
2
3
Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation:There is only one valid cycle highlighted in the image below:

https://assets.leetcode.com/uploads/2020/07/15/2.png

Example 3:

https://assets.leetcode.com/uploads/2020/07/15/3.png

1
2
Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid consists only of lowercase English letters.

Solution:

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
    
        visited = set()
        m, n = len(grid), len(grid[0])
        
        def valid(x, y):
            if 0 <= x < m and 0 <= y < n:
                return True
            return False
        def dfs(node, parent):
            if node in visited: return True
            visited.add(node)
            nx,ny = node
            childs = []
            for cx, cy in [[nx+1,ny],[nx-1, ny],[nx,ny+1],[nx,ny-1]]:
                if valid(cx, cy):
                    if grid[cx][cy] == grid[nx][ny] and (cx,cy) != parent:
                        childs.append((cx, cy))

            for x in childs:
                if dfs(x, node): return True 
            return False  
        
        for i in range(m):
            for j in range(n):
                if (i,j) in visited:
                    continue
                if dfs((i,j), None): 
                    return True
        return False

time complexity: $O()$
space complexity: $O()$
reference:
related problem: