Search a Word in a Letter Grid

medium backtracking grid dfs

Problem

Given a 2D grid of letters and a word, decide whether the word can be traced through 4-adjacent cells without reusing any cell.

Try every cell as a starting point. From there, DFS: if the current letter matches word[k], mark the cell visited (overwrite with '#'), recurse into the four neighbours with k + 1, restore the letter on unwind, and short-circuit on success. Reaching k == len(word) means the trace is complete.

Inputgrid = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"

Outputtrue

Trace: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1).

grid (rows by ';')

word

def exist(grid, word):
    R, C = len(grid), len(grid[0])
    def dfs(r, c, k):
        if k == len(word): return True
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != word[k]:
            return False
        ch = grid[r][c]; grid[r][c] = "#"
        ok = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1)
              or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
        grid[r][c] = ch
        return ok
    for r in range(R):
        for c in range(C):
            if dfs(r, c, 0): return True
    return False

function exist(grid, word) {
  const R = grid.length, C = grid[0].length;
  function dfs(r, c, k) {
    if (k === word.length) return true;
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== word[k]) return false;
    const ch = grid[r][c]; grid[r][c] = "#";
    const ok = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
            || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    grid[r][c] = ch;
    return ok;
  }
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

char[][] g; String w; int R, C;
public boolean exist(char[][] grid, String word) {
    g = grid; w = word; R = grid.length; C = grid[0].length;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (dfs(r, c, 0)) return true;
    return false;
}
boolean dfs(int r, int c, int k) {
    if (k == w.length()) return true;
    if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] != w.charAt(k)) return false;
    char ch = g[r][c]; g[r][c] = '#';
    boolean ok = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
              || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    g[r][c] = ch;
    return ok;
}

int R, C;
bool dfs(vector<vector<char>>& g, string& w, int r, int c, int k) {
    if (k == (int)w.size()) return true;
    if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] != w[k]) return false;
    char ch = g[r][c]; g[r][c] = '#';
    bool ok = dfs(g, w, r + 1, c, k + 1) || dfs(g, w, r - 1, c, k + 1)
           || dfs(g, w, r, c + 1, k + 1) || dfs(g, w, r, c - 1, k + 1);
    g[r][c] = ch;
    return ok;
}
bool exist(vector<vector<char>>& g, string w) {
    R = g.size(); C = g[0].size();
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (dfs(g, w, r, c, 0)) return true;
    return false;
}

Time: O(R · C · 4^L) Space: O(L) recursion