String DP

🧵 String DP: Teaching Strings to Remember Their Transformations

Imagine you’re a magical word wizard who can transform any word into another—but magic costs energy! How do you find the cheapest spell?

🎯 What is String DP?

Think of strings like beaded necklaces. Each bead is a character. String DP helps us answer questions like:

• How many beads must I change to turn one necklace into another?
• Can I break this necklace into smaller pieces that match my bead patterns?
• Does this necklace match a special pattern with wildcards?

The Big Idea: We solve string problems by remembering answers to smaller sub-problems. Like building with LEGO—solve small pieces, then combine them!

graph TD
    A["Big String Problem"] --> B["Smaller Sub-problem 1"]
    A --> C["Smaller Sub-problem 2"]
    B --> D["Even Smaller"]
    C --> D
    D --> E["Base Case: Empty String"]

📏 Edit Distance (Levenshtein Distance)

The Story

Imagine you’re a text message autocorrect wizard. Someone types “KITTEN” but meant “SITTING”. Your job: find the minimum magic spells needed to fix it!

Your Spells:

• 🔄 Replace one letter with another (1 spell)
• ➕ Insert a new letter (1 spell)
• ➖ Delete a letter (1 spell)

Simple Example

Transform “CAT” → “CUT”:

• Just replace ‘A’ with ‘U’
• Answer: 1 operation!

The Magic Table

We build a table where each cell answers: “How many spells to transform the first X letters of word1 into first Y letters of word2?”

        ""  C   U   T
    ""   0  1   2   3
    C    1  0   1   2
    A    2  1   1   2
    T    3  2   2   1  ← Answer!

The Formula (Super Simple!)

For each cell, we pick the cheapest option:

if (char1 == char2) {
    // Characters match! No spell needed
    dp[i][j] = dp[i-1][j-1];
} else {
    // Pick cheapest: Replace, Insert, or Delete
    dp[i][j] = 1 + min(
        dp[i-1][j-1],  // Replace
        dp[i][j-1],    // Insert
        dp[i-1][j]     // Delete
    );
}

Java Code

public int editDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Base cases: empty string transformations
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i-1][j-1],
                    Math.min(dp[i][j-1], dp[i-1][j])
                );
            }
        }
    }
    return dp[m][n];
}

Time: O(m × n) | Space: O(m × n)

🧩 Word Break

The Story

You receive a mysterious message with no spaces: "ilikecoding"

You have a dictionary of words: ["i", "like", "coding", "code", "ice"]

Can you break it into real words? → “i like coding” ✅

Simple Example

String: "applepenapple" Dictionary: ["apple", "pen"]

Break it: “apple” + “pen” + “apple” ✅

The Magic Idea

For each position, ask: “Can everything before this point be broken into words, AND does a dictionary word end here?”

graph TD
    A["applepenapple"] --> B["apple|penapple"]
    B --> C["apple|pen|apple"]
    C --> D["✅ All valid words!"]

The Formula

dp[i] = true if there exists some j where:
    - dp[j] is true (everything before j is breakable)
    - substring from j to i is in dictionary

Java Code

public boolean wordBreak(String s, List<String> dict) {
    Set<String> words = new HashSet<>(dict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;  // Empty string is valid

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            String sub = s.substring(j, i);
            if (dp[j] && words.contains(sub)) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

Time: O(n² × k) where k is average word length | Space: O(n)

🃏 Wildcard Matching

The Story

You’re playing a card matching game with special wild cards:

• ? matches any single character (like a joker that becomes ONE card)
• * matches any sequence (including nothing!)

Simple Example

Pattern: "c*t" Strings that match: “cat”, “coat”, “ct”, “coconut”

Pattern: "c?t" Strings that match: “cat”, “cut”, “cot” (exactly 3 letters)

The Magic Table

Each cell answers: “Does pattern[0…i] match string[0…j]?”

        ""  c   a   t
    ""   ✅  ❌  ❌  ❌
    c    ❌  ✅  ❌  ❌
    *    ✅  ✅  ✅  ✅
    t    ❌  ❌  ❌  ✅

The Formula

if (pattern[i] == '*') {
    // * matches empty OR * matches current char
    dp[i][j] = dp[i-1][j] || dp[i][j-1];
} else if (pattern[i] == '?' || pattern[i] == string[j]) {
    // Direct match or ? wildcard
    dp[i][j] = dp[i-1][j-1];
} else {
    dp[i][j] = false;
}

Java Code

public boolean wildcardMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;

    // Handle leading *'s
    for (int i = 1; i <= n; i++) {
        if (p.charAt(i-1) == '*') {
            dp[i][0] = dp[i-1][0];
        }
    }

    for (int i = 1; i <= n; i++) {
        char pc = p.charAt(i-1);
        for (int j = 1; j <= m; j++) {
            if (pc == '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            } else if (pc == '?' || pc == s.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[n][m];
}

Time: O(m × n) | Space: O(m × n)

🎭 Regular Expression Matching

The Story

This is Wildcard Matching’s bigger brother! Now we have:

• . matches any single character (same as ?)
• * means “zero or more of the previous character”

Key Difference: In regex, * doesn’t stand alone—it modifies the character before it!

Simple Example

Pattern: "a*b" Matches: “b”, “ab”, “aab”, “aaaaaab” (The a* means zero or more 'a’s)

Pattern: ".*" Matches: ANYTHING! (any character, any number of times)

The Tricky Part

c* can match:

• “” (zero c’s)
• “c” (one c)
• “cc” (two c’s)
• “cccc…” (many c’s)

The Formula

if (pattern[i] == '*') {
    // Option 1: Use zero of previous char
    dp[i][j] = dp[i-2][j];
    // Option 2: Previous char matches current
    if (pattern[i-1] == '.' || pattern[i-1] == string[j]) {
        dp[i][j] = dp[i][j] || dp[i][j-1];
    }
} else if (pattern[i] == '.' || pattern[i] == string[j]) {
    dp[i][j] = dp[i-1][j-1];
}

Java Code

public boolean regexMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;

    // Handle patterns like a*, a*b*, etc.
    for (int i = 2; i <= n; i++) {
        if (p.charAt(i-1) == '*') {
            dp[i][0] = dp[i-2][0];
        }
    }

    for (int i = 1; i <= n; i++) {
        char pc = p.charAt(i-1);
        for (int j = 1; j <= m; j++) {
            if (pc == '*') {
                char prev = p.charAt(i-2);
                // Zero occurrences
                dp[i][j] = dp[i-2][j];
                // One or more occurrences
                if (prev == '.' || prev == s.charAt(j-1)) {
                    dp[i][j] = dp[i][j] || dp[i][j-1];
                }
            } else if (pc == '.' || pc == s.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[n][m];
}

Time: O(m × n) | Space: O(m × n)

🔑 Pattern Recognition: When to Use What?

🚀 Pro Tips

1. Always handle base cases first - Empty strings need special care!
2. Draw the DP table - It helps visualize the problem.
3. Space optimization - Many string DP can use O(n) instead of O(m×n).
4. Practice the patterns - These 4 problems cover 90% of string DP!

🎯 Quick Recap

graph TD
    A["String DP Patterns"] --> B["Edit Distance"]
    A --> C["Word Break"]
    A --> D["Wildcard Matching"]
    A --> E["Regex Matching"]

    B --> F["Transform A→B<br>Min operations"]
    C --> G["Can break into<br>dictionary words?"]
    D --> H["? = one char<br>* = any sequence"]
    E --> I[". = one char<br>* = repeat previous"]

Remember: All these problems share the same DNA:

1. Define what dp[i][j] means
2. Find the recurrence relation
3. Handle base cases
4. Fill the table!

You’ve got this! 🌟