Ankit Kashyap

Strings and Grids

Strings and Grids

These problems are not about choosing a number from an array, but they use the same shape:

  • build a valid sequence one character at a time;
  • choose one letter for the next output position;
  • choose the next valid substring;
  • choose the next grid neighbor.

The DFS state must describe how much of the input has been consumed and which current-path restrictions apply.

Pattern summary

ProblemDFS stateOne branch meansImportant invariant
Generate Parenthesesopen count, close countadd one legal parenthesiscloses never exceed opens
Letter Combinationsdigit indexchoose one mapped letterpath length equals processed digits
Palindrome Partitioningstring start indexchoose one valid next piecepath pieces exactly cover the prefix
Word Searchrow, column, word indexmove to one adjacent matching cella cell is visited only in the current path

9. Generate Parentheses

Problem

Recognition

Build a string of n opening and n closing parentheses, but never create a prefix that cannot be repaired. The two legal choices are determined by counts:

  • add "(" while fewer than n opens have been used;
  • add ")" only while close < open.

The second condition is the key invariant: every prefix has at least as many opens as closes.

DFS contract

dfs(open, close) adds every valid completion of the current path, which already contains open opening and close closing parentheses.

JavaScript

function generateParenthesis(n) {
  const result = [];
  const path = [];
 
  function dfs(open, close) {
    if (open === n && close === n) {
      result.push(path.join(""));
      return;
    }
 
    if (open < n) {
      path.push("(");
      dfs(open + 1, close);
      path.pop();
    }
 
    if (close < open) {
      path.push(")");
      dfs(open, close + 1);
      path.pop();
    }
  }
 
  dfs(0, 0);
  return result;
}

Why no invalid strings are generated

A closing parenthesis is never chosen unless there is an unmatched opening parenthesis to pair it with. At the final length, the string therefore has equal counts and every prefix is balanced—exactly the definition of a valid parenthesis string.

  • Time: O(Cn * n), where Cn is the nth Catalan number (the number of valid answers).
  • Auxiliary space: O(n), excluding output.

10. Letter Combinations of a Phone Number

Problem

Recognition

Each digit independently offers three or four letters. This is a simple product-of-choices tree: one letter per digit position.

DFS contract

dfs(i) generates every letter string whose prefix is path, after making choices for digits before index i.

JavaScript

function letterCombinations(digits) {
  if (digits.length === 0) return [];
 
  const letters = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
 
  const result = [];
  const path = [];
 
  function dfs(i) {
    if (i === digits.length) {
      result.push(path.join(""));
      return;
    }
 
    for (const letter of letters[digits[i]]) {
      path.push(letter);
      dfs(i + 1);
      path.pop();
    }
  }
 
  dfs(0);
  return result;
}
  • Time: O(n * 4^n) — at most four choices per digit and O(n) to build each returned string.
  • Auxiliary space: O(n), excluding output.

11. Palindrome Partitioning

Problem

Recognition

At the current string index, the decision is not “take or skip a character.” It is:

Where should the next cut end?

Try every ending position, but recurse only when the chosen substring is a palindrome.

DFS contract

dfs(start) produces every palindrome partition of the suffix beginning at start; path already partitions s[0...start - 1].

JavaScript

function partition(s) {
  const result = [];
  const path = [];
 
  function isPalindrome(left, right) {
    while (left < right) {
      if (s[left] !== s[right]) return false;
      left++;
      right--;
    }
    return true;
  }
 
  function dfs(start) {
    if (start === s.length) {
      result.push([...path]);
      return;
    }
 
    for (let end = start; end < s.length; end++) {
      if (!isPalindrome(start, end)) continue;
 
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  }
 
  dfs(0);
  return result;
}

Correctness cue

Every recursive call moves start to exactly one position after the selected piece. Therefore the path contains contiguous, non-overlapping pieces that cover the original string exactly when start === s.length.

  • Time: O(n * 2^n) in the usual output-sensitive bound.
  • Auxiliary space: O(n) for recursion and path, excluding output.
  • Upgrade path: precompute a palindrome table when palindrome checks become the bottleneck.

Problem

Recognition

The word may start anywhere, so launch DFS from every cell. A path may move up, down, left, or right, but may not reuse a cell in that one path.

DFS contract

dfs(r, c, i) returns whether a path beginning at (r, c) can match word[i...]. Before it runs, cells on the route to this one are marked visited.

JavaScript

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
 
  function dfs(r, c, i) {
    if (i === word.length) return true;
 
    if (
      r < 0 || r === rows ||
      c < 0 || c === cols ||
      board[r][c] !== word[i]
    ) {
      return false;
    }
 
    const saved = board[r][c];
    board[r][c] = "#"; // mark this cell for this path only
 
    const found =
      dfs(r + 1, c, i + 1) ||
      dfs(r - 1, c, i + 1) ||
      dfs(r, c + 1, i + 1) ||
      dfs(r, c - 1, i + 1);
 
    board[r][c] = saved; // always restore before returning
    return found;
  }
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
 
  return false;
}

Why restoration matters even after success

The found expression evaluates the needed branches, then the function restores the cell before returning its boolean answer. That preserves the input and keeps the DFS contract true. Returning directly from a branch before restoration is a common bug.

  • Time: O(rows * cols * 4 * 3^(L - 1)), where L is word length.
  • Auxiliary space: O(L) recursion / current path.

Practical pruning

Before DFS, return false if the word is longer than the number of cells. You can also compare character frequencies in the board and word, or reverse the word to begin with its rarer endpoint. These reduce work but do not change the recurrence.

Recall prompts

ProblemSay this before coding
Generate Parentheses“Add an open if I can; add a close only if it can match an earlier open.”
Phone combinations“At each digit, choose one mapped letter and advance one position.”
Palindrome partitioning“At each start index, try every next cut that forms a palindrome.”
Word Search“From every start cell, match one character, mark the cell, explore four neighbors, then restore it.”

Next: 05 - Constraint Search

Backlinks