Why Word Search in Grid Using Backtracking in DSA C?

The Big Idea

What if you could find any hidden word in a grid without missing a single path or getting lost?

The Scenario

Imagine you have a big crossword puzzle on paper, and you want to find if a certain word is hidden inside it by checking every letter manually.

You look at each letter, then try to see if the next letters match the word by moving up, down, left, or right.

This takes a lot of time and you can easily lose track or miss some paths.

The Problem

Manually checking every possible path for the word is slow and confusing.

You might forget which letters you already checked or accidentally reuse letters that should only be used once.

It's easy to make mistakes and miss the word even if it's there.

The Solution

Backtracking is like having a smart helper who tries every possible path step-by-step.

If the path doesn't lead to the word, the helper goes back and tries a different path.

This way, you don't miss any possibilities and avoid repeating letters incorrectly.

Before vs After

✗ Before

for each cell in grid:
  if cell matches first letter:
    check all directions manually

✓ After

bool searchWord(grid, word, row, col, index) {
  if (index == word length) return true;
  if (row < 0 || col < 0 || row >= grid rows || col >= grid cols || grid[row][col] != word[index]) return false;
  mark cell visited;
  for each direction {
    if (searchWord(next cell, index + 1)) return true;
  }
  unmark cell;
  return false;
}

What It Enables

You can efficiently find if a word exists in a grid by exploring all paths without missing or repeating letters wrongly.

Real Life Example

Finding hidden words in a word search puzzle game on your phone, where letters can be connected in multiple directions.

Key Takeaways

Manual search is slow and error-prone for word search in grids.

Backtracking tries all paths systematically and backtracks on dead ends.

This method ensures all possibilities are checked correctly and efficiently.