Detect Cycles in 2D Grid LeetCode solution in Java

1
class Solution {
2
  public boolean containsCycle(char[][] grid) {
3
    int rows = grid.length, cols = grid[0].length;
4

5
    // Create a boolean array of same dimensions to keep track of visited cells
6
    boolean[][] visited = new boolean[rows][cols];
7

8
    for (int i = 0; i < rows; i++) {
9
      for (int j = 0; j < cols; j++) {
10
        if (!visited[i][j] && dfs(grid, visited, i, j, 0, 0, grid[i][j])) {
11
          return true;
12
        }
13
      }
14
    }
15

16
    return false;
17
  }
18

19
  public boolean dfs(
20
      char[][] grid, boolean[][] visited, int i, int j, int prevI, int prevJ, char c) {
21
    // Check for out of bounds
22
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return false;
23

24
    // Check whether the current char matches the previous char
25
    if (grid[i][j] != c) return false;
26

27
    // If we stumble upon the same cell, we're guaranteed to have found a cycle!
28
    if (visited[i][j]) {
29
      return true;
30
    }
31

32
    // Mark the cell as visited
33
    visited[i][j] = true;
34

35
    // We want to search in the south direction ONLY IF we didn't come from north
36
    // Do the same for all four directions
37
    boolean south = i - prevI != -1;
38
    boolean north = i - prevI != 1;
39
    boolean east = j - prevJ != -1;
40
    boolean west = j - prevJ != 1;
41
    return (south && dfs(grid, visited, i + 1, j, i, j, c))
42
        || (north && dfs(grid, visited, i - 1, j, i, j, c))
43
        || (east && dfs(grid, visited, i, j + 1, i, j, c))
44
        || (west && dfs(grid, visited, i, j - 1, i, j, c));
45
  }
46
}