TRT
Sign in

Advanced · Module 15 · Lesson 4 of 6

Grids and strings

Two-dimensional DP fills a table whose cells depend on their neighbors above and to the left. On grids it counts or optimizes paths; on two strings, a cell compares two prefixes, which is how diff tools, spell checkers and DNA alignment work.

Pro — members onlyAbout 15 minutes

By the end you can

  • Fill a grid DP row by row for path counting and path costs
  • Define dp[i][j] on prefixes of two strings and derive the longest common subsequence and edit distance recurrences
  • Read a recurrence off the last characters of the two prefixes

Builds on One-dimensional problems.

01 · A question first

A spell checker suggests "sitting" for "kitten" because only three edits separate them. Trying every sequence of edits is hopeless, but a 7 × 8 table filled row by row finds the minimum. What does each cell of that table mean?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Two dimensions
  • Paths through a grid
  • Two strings, two prefixes
  • Choosing the state for two sequences
  • Where these tables run
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeUnique pathsCount the paths from the top-left to the bottom-right of a grid moving only right or down, with a grid DP.Practice · medium · LeetCodeUnique paths IICount right-and-down paths through a grid with obstacles, setting blocked cells to zero.Practice · medium · LeetCodeLongest common subsequenceFind the length of the longest subsequence shared by two strings with a table over their prefixes.Practice · hard · LeetCodeDistinct subsequencesCount how many times t appears as a subsequence of s with a two-string counting DP.Practice · medium · LeetCodeLongest palindromic subsequenceFind the longest subsequence of a string that reads the same backward, with an interval DP on the string's two ends.Practice · hard · LeetCodeRegular expression matchingMatch a string against a pattern with . and * using a table over string and pattern prefixes.

Asked in interviews

Something wrong with this lesson? Report a problem