Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Start a DFS from every cell whose letter equals word[0].
  2. 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");
    }
}

Solve Word Search online · All practice problems