String DP

String DP: The Art of Transforming Words 🪄

The Magic Spell Book Analogy

Imagine you have a magic spell book. Each spell can transform one word into another. But magic costs energy! The best wizards find spells that use the least energy to make transformations.

String DP is exactly like this. We figure out the smartest way to:

• Change one word into another (Edit Distance)
• Break words into pieces (Word Break)
• Match patterns with wildcards (Wildcard Matching)
• Handle complex patterns (Regular Expression Matching)

What is DP on Strings?

Dynamic Programming on Strings means solving problems by:

1. Looking at small pieces of strings first
2. Building up answers to bigger pieces
3. Using a table to remember what we already solved

The Simple Idea

Think of two words as train tracks running side by side.

Word 1:  C - A - T
Word 2:  C - U - T

We compare them character by character. Each comparison gives us a small answer. We combine small answers into the big answer!

1. Edit Distance (Levenshtein Distance)

The Story

You’re a text message fixer. Your friend types “KITTEN” but meant “SITTING”. How many fixes do you need?

A fix can be:

• Insert a letter
• Delete a letter
• Replace a letter

Visual Journey

graph TD
    A["KITTEN"] --> B["SITTEN<br/>Replace K→S"]
    B --> C["SITTIN<br/>Replace E→I"]
    C --> D["SITTING<br/>Insert G"]

Answer: 3 fixes!

How It Works

We build a table. Each cell answers: “How many edits to change first X letters into first Y letters?”

        ""  S   I   T   T   I   N   G
    ""   0   1   2   3   4   5   6   7
    K    1   1   2   3   4   5   6   7
    I    2   2   1   2   3   4   5   6
    T    3   3   2   1   2   3   4   5
    T    4   4   3   2   1   2   3   4
    E    5   5   4   3   2   2   3   4
    N    6   6   5   4   3   3   2   3

Bottom-right = 3 ✨

The Magic Formula

For each cell, we pick the smallest of:

if s1[i] == s2[j]:
    dp[i][j] = dp[i-1][j-1]  # Same letter, no cost!
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],    # Delete
        dp[i][j-1],    # Insert
        dp[i-1][j-1]   # Replace
    )

Real Example

Change “CAT” to “CUT”:

Answer: 1 (just replace A with U)

2. Word Break

The Story

Imagine you receive a message with no spaces:

"ilikecoding"

Can you break it into real words from a dictionary?

Dictionary: [“i”, “like”, “coding”, “code”, “ice”, “cream”]

Answer: “i” + “like” + “coding” = ✅ Yes!

The Challenge

"catsanddog" with [“cat”, “cats”, “and”, “sand”, “dog”]

Multiple ways exist:

• “cats” + “and” + “dog”
• “cat” + “sand” + “dog”

How It Works

We check every position: “Can I reach here using dictionary words?”

graph TD
    A["Position 0<br/>Start ✅"] --> B["Position 1<br/>'i' found ✅"]
    B --> C["Position 5<br/>'like' found ✅"]
    C --> D["Position 11<br/>'coding' found ✅"]

The Simple Code Idea

def wordBreak(s, wordDict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string = valid!

    for i in range(1, n + 1):
        for word in wordDict:
            wlen = len(word)
            if i >= wlen:
                # Check if word fits here
                if dp[i - wlen]:
                    if s[i - wlen:i] == word:
                        dp[i] = True
                        break

    return dp[n]

Walk Through “leetcode”

Dictionary: [“leet”, “code”]

Answer: True! 🎉

3. Wildcard Matching

The Story

You’re playing a guessing game. You have pattern cards:

• ? = matches any single letter
• * = matches anything (even nothing!)

Pattern: "c*t"

Matches: “cat”, “cut”, “cart”, “ct”, “coconut”

The Tricky Part

* is greedy! It can match zero letters or many letters.

Pattern: "a*b"

• “ab” ✅ (* matches nothing)
• “aXb” ✅ (* matches “X”)
• “aXXXb” ✅ (* matches “XXX”)
• “abc” ❌ (doesn’t end with b)

Visual Example

graph TD
    A["Pattern: a*b<br/>Text: aXYb"] --> B["'a' matches 'a' ✅"]
    B --> C["'*' matches 'X'"]
    C --> D["'*' matches 'Y'"]
    D --> E["'b' matches 'b' ✅"]

The DP Table Approach

Build a table where dp[i][j] = “Does pattern[0:i] match text[0:j]?”

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1)
          for _ in range(m + 1)]

    dp[0][0] = True

    # Handle leading stars
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Star matches empty OR
                # one more character
                dp[i][j] = (dp[i][j-1] or
                            dp[i-1][j])
            elif p[j-1] == '?' or \
                 p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[m][n]

Quick Example

Pattern: "?a*" Text: "bat"

Answer: True! ✨

4. Regular Expression Matching

The Story

This is Wildcard Matching’s older sibling. More powerful, more complex!

Special characters:

• . = matches any single character (like ?)
• * = the letter before it can appear 0 or more times

The Key Difference

In regex, * doesn’t stand alone. It modifies the previous character!

Examples

Visual Flow

graph TD
    A["Pattern: a*b<br/>Text: aaab"] --> B["'a*' matches 'aaa'"]
    B --> C["'b' matches 'b' ✅"]

The DP Solution

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1)
          for _ in range(m + 1)]

    dp[0][0] = True

    # Handle patterns like a*, a*b*, etc.
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Option 1: ignore x* entirely
                dp[i][j] = dp[i][j-2]
                # Option 2: use x* if matches
                if p[j-2] == '.' or \
                   p[j-2] == s[i-1]:
                    dp[i][j] = (dp[i][j] or
                                dp[i-1][j])
            elif p[j-1] == '.' or \
                 p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[m][n]

Step Through “aa” with “a*”

Why is dp[2][2] = True?

a* means “zero or more a’s”. Two a’s? Perfect match! ✅

Comparing the Four Patterns

The Universal DP Recipe

All four problems follow the same recipe:

1. Create a table (usually 2D)
2. Define base cases (empty strings)
3. Fill cell by cell (small to big)
4. Return the answer (usually bottom-right)

Memory Trick

Think of it as filling a spreadsheet:

• Rows = characters from string 1
• Columns = characters from string 2 (or pattern)
• Each cell = answer for that prefix combination

Practice Problems to Try

1. Edit Distance: “horse” → “ros” (Answer: 3)
2. Word Break: “applepenapple” with [“apple”, “pen”]
3. Wildcard: Pattern “a*c?e” on “abcde”
4. Regex: Pattern “.*” matches everything!

You’ve Got This! 🚀

String DP might seem scary at first. But now you know:

• It’s just comparing characters step by step
• We use tables to avoid repeating work
• Each problem has its own special rules

Start with Edit Distance. It’s the friendliest. Once that clicks, the others will follow!

Remember: Every expert was once a beginner. Keep practicing! 💪