MEDIUM NC#76 Blind #49 Backtracking / DFS

79. Word Search

📖 Problem

Given an m x n 2D board of characters 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 neighboring. The same letter cell may not be used more than once in a word.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Recursive stack flow
  • •Cycle prevention
  • •Post-order reasoning

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply DFS reasoning pattern
  • •Apply Backtracking reasoning pattern

💡 Approach

  • → Use DFS to search for word starting from each cell
  • → Track visited cells to avoid infinite loops
  • → Try all 4 directions (up, down, left, right)
  • → Time: O(m * n * 4^L) worst case

🛠️ Hints & Pitfalls

Hints

  • •Use DFS to search for word starting from each cell
  • •Track visited cells to avoid infinite loops
  • •Try all 4 directions (up, down, left, right)

Common Pitfalls

  • •Time: O(m * n * 4^L) worst case

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED');
Expected:
false
Test Case 2
Not run
Input:
exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE');
Expected:
false
Test Case 3
Not run
Input:
exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCB');
Expected:
false

📝 Code Editor

📚 Reference Solution

▼
⌘K Search ⌘↩ Run ⌘S Submit