Word Search in Grid Using Backtracking in DSA Typescript - Build from Scratch

Word Search in Grid Using Backtracking

📖 Scenario: You are building a simple word search puzzle solver. The puzzle is a grid of letters, and you want to find if a given word exists in the grid by moving horizontally or vertically to adjacent letters.This is like searching for a hidden word in a crossword puzzle.

🎯 Goal: Build a program that checks if a given word can be found in the letter grid by moving up, down, left, or right, without revisiting the same cell twice.

📋 What You'll Learn

Create a 2D array called board with exact letters

Create a string variable called word with the exact word to search

Write a function exist that returns true if the word is found in the board, else false

Use backtracking to explore possible paths in the grid

Print the result of exist(board, word)

💡 Why This Matters

🌍 Real World

Word search puzzles and games often require searching for words hidden in grids of letters. This technique helps solve or generate such puzzles.

💼 Career

Backtracking and grid traversal are common in technical interviews and real-world problems like pathfinding, puzzle solving, and game development.

1

Create the letter grid

Create a 2D array called board with these exact rows: ['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']

DSA Typescript

// Create the 2D array called board with the exact letters
// Your code here

Hint

Use a constant variable board and assign a 2D array with the exact letters as rows.

2

Set the word to search

Create a string variable called word and set it to the exact value 'ABCCED'

DSA Typescript

const board: string[][] = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
];

// Create the string variable word with value 'ABCCED'
// Your code here

Hint

Use const word: string = 'ABCCED'; to set the word.

3

Write the backtracking function to find the word

Write a function called exist that takes board: string[][] and word: string and returns true if the word exists in the board by moving horizontally or vertically. Use backtracking with a helper function dfs inside exist. Use variables rows, cols, and a 2D boolean array visited to track visited cells. Use for loops and recursion to explore neighbors.

DSA Typescript

const board: string[][] = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
];

const word: string = 'ABCCED';

// Write the function exist(board: string[][], word: string): boolean with backtracking
// Your code here

Hint

Use a helper function dfs inside exist to explore neighbors recursively. Mark cells visited before recursion and unmark after.

4

Print the result of the word search

Write a console.log statement to print the result of calling exist(board, word)

DSA Typescript

Hint

Use console.log(exist(board, word)); to print the result.