Practice › Recursion & Backtracking
Word Search
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Meta, Bloomberg, Uber
Can word be built from letters of sequentially adjacent cells (up, down, left, right) in the grid, using each cell at most once? Print YES or NO.
Input
First line: r c. Next r lines: the grid rows (strings of c uppercase letters). Last line: word.
Output
YES or NO.
Constraints
- 1 ≤ r, c ≤ 6
- 1 ≤ |word| ≤ 15
DFS from every cell that matches the first letter. Mark a cell as used while it is on the current path and unmark it when you backtrack.
Example 1
Input
3 4 ABCE SFCS ADEE ABCCED
Output
YES
Example 2
Input
3 4 ABCE SFCS ADEE ABCB
Output
NO
Hints
- Start a DFS from every cell whose letter equals word[0].
- In the DFS, mark the current cell as used before exploring the 4 neighbours for the next letter, and unmark it when returning (backtracking).
Approach
dfs(i, j, k) returns true if word[k..] can be traced starting at cell (i, j). It fails if the cell is outside the grid, already on the path, or has the wrong letter. Otherwise mark it, try the four neighbours with k + 1, then unmark. Reaching k == |word| means success. The marking prevents reusing a cell in the same path.
Complexity: O(r · c · 3^L) worst case (L = word length) · O(L) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<string> g;
string w;
vector<vector<bool>> used;
bool dfs(int i, int j, int k) {
if (k == (int)w.size()) return true;
if (i < 0 || j < 0 || i >= R || j >= C || used[i][j] || g[i][j] != w[k]) return false;
used[i][j] = true;
bool ok = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
used[i][j] = false;
return ok;
}
int main() {
cin >> R >> C;
g.resize(R);
for (auto &row : g) cin >> row;
cin >> w;
used.assign(R, vector<bool>(C, false));
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (dfs(i, j, 0)) {
cout << "YES\n";
return 0;
}
cout << "NO\n";
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
g = data[2 : 2 + R]
w = data[2 + R]
used = [[False] * C for _ in range(R)]
def dfs(i, j, k):
if k == len(w):
return True
if i < 0 or j < 0 or i >= R or j >= C or used[i][j] or g[i][j] != w[k]:
return False
used[i][j] = True
ok = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
used[i][j] = False
return ok
print("YES" if any(dfs(i, j, 0) for i in range(R) for j in range(C)) else "NO")Java solution
import java.util.*;
public class Main {
static int R, C;
static String[] g;
static String w;
static boolean[][] used;
static boolean dfs(int i, int j, int k) {
if (k == w.length()) return true;
if (i < 0 || j < 0 || i >= R || j >= C || used[i][j] || g[i].charAt(j) != w.charAt(k)) return false;
used[i][j] = true;
boolean ok = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
used[i][j] = false;
return ok;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
g = new String[R];
for (int i = 0; i < R; i++) g[i] = sc.next();
w = sc.next();
used = new boolean[R][C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (dfs(i, j, 0)) {
System.out.println("YES");
return;
}
System.out.println("NO");
}
}