Ankit Kashyap

2D String problems

Two-String DP — dfs(i, j) Pattern

Problem List

#ProblemLeetCodeDifficulty
1Longest Common Subsequencehttps://leetcode.com/problems/longest-common-subsequence/Medium
2Interleaving Stringhttps://leetcode.com/problems/interleaving-string/Medium
3Distinct Subsequenceshttps://leetcode.com/problems/distinct-subsequences/Hard
4Edit Distancehttps://leetcode.com/problems/edit-distance/Medium
5Wildcard Matchinghttps://leetcode.com/problems/wildcard-matching/Hard
6Regular Expression Matchinghttps://leetcode.com/problems/regular-expression-matching/Hard

Core Pattern

Most of these problems can be expressed as:

dfs(i, j)

where i and j represent positions in two strings, or a string and a pattern.

The main question at every state:

Do the current characters match? If yes/no, which pointer(s) should move?

Memoizing (i, j) generally gives O(m × n) states.

1. Longest Common Subsequence — LC 1143

State

dfs(i, j)

Length of the LCS between text1[i:] and text2[j:].

Transition

If characters match:

1 + dfs(i + 1, j + 1)

Otherwise, skip one character from either string:

Math.max(
    dfs(i + 1, j),
    dfs(i, j + 1)
)

Base case

if (i === s1.length || j === s2.length)
    return 0;

Remember

match    → take it, move both
no match → skip from either side

Complexity: O(m × n)

2. Interleaving String — LC 97

Given s1, s2, determine whether they can be interleaved to create s3.

State

dfs(i, j)

i = position in s1
j = position in s2

Position in s3 is automatically:

k = i + j

Transition

Try taking from s1:

if (s1[i] === s3[i + j])
    dfs(i + 1, j)

Try taking from s2:

if (s2[j] === s3[i + j])
    dfs(i, j + 1)

If either works → true.

Important optimization

Immediately reject:

if (s1.length + s2.length !== s3.length)
    return false;

Remember

s3[k]
  ↓
Can I take s1[i]?
OR
Can I take s2[j]?

Complexity: O(m × n)

3. Distinct Subsequences — LC 115

Count how many subsequences of s equal t.

State

dfs(i, j)

Number of ways s[i:] can produce t[j:].

If characters match

Two choices:

dfs(i + 1, j + 1)  // use s[i]
+
dfs(i + 1, j)      // skip s[i]

If they don’t match

Only skip:

dfs(i + 1, j)

Base cases

Successfully constructed all of t:

if (j === t.length)
    return 1;

Ran out of s:

if (i === s.length)
    return 0;

Remember

match    → TAKE + SKIP
no match → SKIP

This is the classic take/skip subsequence DP.

Complexity: O(m × n)

4. Edit Distance — LC 72

Find minimum operations required to transform word1 into word2.

Allowed operations:

  • Insert
  • Delete
  • Replace

State

dfs(i, j)

Minimum operations to convert word1[i:] → word2[j:].

If characters match

No operation needed:

dfs(i + 1, j + 1)

If characters don’t match

1 + Math.min(
    dfs(i, j + 1),      // insert
    dfs(i + 1, j),      // delete
    dfs(i + 1, j + 1)   // replace
)

Base cases

If word1 is exhausted:

return word2.length - j;

If word2 is exhausted:

return word1.length - i;

Remember

              mismatch
                 |
       +---------+---------+
       |         |         |
     Insert    Delete    Replace
     i,j+1     i+1,j     i+1,j+1

Complexity: O(m × n)

5. Wildcard Matching — LC 44

Pattern supports:

? → exactly one arbitrary character
* → zero or more arbitrary characters

State

dfs(i, j)

Does s[i:] match p[j:]?

Normal character / ?

match && dfs(i + 1, j + 1)

where:

match = s[i] === p[j] || p[j] === "?";

When p[j] === "*"

Two choices:

dfs(i, j + 1) ||
dfs(i + 1, j)

Meaning:

dfs(i, j + 1) → * matches nothing
dfs(i + 1, j) → * consumes one character

Stay at j after consuming because * can consume more.

Remember

* → SKIP or CONSUME
 
skip    → j + 1
consume → i + 1

Complexity: O(m × n)

6. Regular Expression Matching — LC 10

Pattern supports:

. → exactly one arbitrary character
* → zero or more of PREVIOUS element

Examples:

a* → "", "a", "aa", "aaa"...
.* → any sequence

State

dfs(i, j)

Does s[i:] match p[j:]?

Current character matches when:

match =
    i < s.length &&
    (s[i] === p[j] || p[j] === ".");

Normal character / .

match && dfs(i + 1, j + 1)

If next character is *

if (p[j + 1] === "*")

Two choices:

dfs(i, j + 2) ||
(match && dfs(i + 1, j))

Meaning:

dfs(i, j + 2)
→ use x* zero times
 
dfs(i + 1, j)
→ consume one matching character
   and keep x* available

Remember

x* → SKIP or CONSUME
 
skip    → j + 2
consume → i + 1, stay at j

Complexity: O(m × n)

Wildcard vs Regex — Important Difference

This is the easiest place to get confused.

Wildcard

* = any sequence of characters

Transition:

dfs(i, j + 1) || dfs(i + 1, j)
skip *   → j + 1
consume  → i + 1

Regex

* = repeat PREVIOUS element

For a*:

dfs(i, j + 2) || (match && dfs(i + 1, j))
skip a*  → j + 2
consume  → i + 1

Quick memory trick

WILDCARD:  * itself is powerful
REGEX:     character BEFORE * is repeated

Final Cheat Sheet

LCS
match    → 1 + dfs(i+1,j+1)
no match → max(dfs(i+1,j), dfs(i,j+1))
 
 
INTERLEAVING
take s1 → dfs(i+1,j)
take s2 → dfs(i,j+1)
 
 
DISTINCT SUBSEQUENCES
match    → TAKE + SKIP
no match → SKIP
 
 
EDIT DISTANCE
match    → dfs(i+1,j+1)
 
mismatch →
1 + min(
    insert  → dfs(i,j+1),
    delete  → dfs(i+1,j),
    replace → dfs(i+1,j+1)
)
 
 
WILDCARD
normal/? → dfs(i+1,j+1)
 
* →
skip    → dfs(i,j+1)
consume → dfs(i+1,j)
 
 
REGEX
normal/. → dfs(i+1,j+1)
 
x* →
skip    → dfs(i,j+2)
consume → dfs(i+1,j)

The Common Mental Model

For all six:

              dfs(i, j)
                  |
          Do chars match?
             /        \
           YES         NO
            |           |
      Which pointer   What choices
      should move?    are available?

When you see two strings, string transformation, subsequence matching, or pattern matching, consider a 2D DP state like dfs(i, j) early.