Word Search

Asked byAmazonTwitterUberKaratMicrosoftBloomberg

Problem

Given an m x n grid of characters and a word, determine whether the word can be constructed from a path of adjacent cells, moving up, down, left or right, without reusing the same cell more than once.

Examples

Example 1

Input:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output:true

Example 2

Input:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output:false

Constraints

1 <= board rows/cols <= 6

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Backtracking pattern

Explore a decision one choice at a time, undo it if it doesn't lead anywhere, and try the next option. It's a systematic way to generate every valid combination, permutation, or arrangement.

Look for this pattern when

The problem asks for "all possible" combinations, subsets, permutations, or valid arrangements.
A greedy or direct-formula approach doesn't work because you genuinely need to explore multiple branches.

Read the full Backtracking guide →

Video walkthroughs

Original problem on LeetCode ↗