DSA problem
Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once in a single match.
The brute-force approach is exponential by nature: from any starting cell whose character matches word[0], branch into up to four neighbouring cells looking for the next character, and so on. Without pruning this would be O(m * n * 4^L) in the worst case, where L is the length of the word.
The optimal algorithm is backtracking with in-place marking. At each step we check the character match first (the cheapest test) and only then recurse into the neighbours. To prevent the same cell from being reused within a single path, we temporarily overwrite the character with a sentinel (for example #) before recursing and restore it after the recursion returns. This keeps space at O(L) for the recursion stack without an auxiliary visited matrix.
In practice the search is much faster than the worst case because mismatched characters prune entire subtrees immediately. Choosing the right starting cell — typically the rarest character in the word — gives a further constant-factor speed-up but is not required for correctness.
Examples
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"trueboard = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"trueboard = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"falseConstraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consist of only lowercase and uppercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.