String DP

String DP: The Magic Spell Book of Text Transformation

The Story of the String Wizard

Imagine you have a magic spell book. This book can transform any word into any other word, break sentences into dictionary words, and even understand wildcard patterns like a fortune teller. That’s exactly what String DP does!

String DP = Using dynamic programming to solve problems involving strings (text).

Think of it like building with LEGO bricks. Each small piece connects to make something bigger. We solve tiny problems first, then combine them to solve the big problem!

1. DP on Strings - The Foundation

What Does “DP on Strings” Mean?

Imagine you’re reading a book. Instead of understanding the whole book at once, you:

1. Read one word
2. Then two words together
3. Keep building until you understand everything

That’s DP on Strings!

We create a table (like a game board) where:

• Each cell stores an answer to a small question
• We fill the table step by step
• The final cell gives us the answer!

Simple Example: Longest Common Subsequence

Question: What letters do “CAT” and “CUT” share in order?

    ""  C   U   T
""   0  0   0   0
C    0  1   1   1
A    0  1   1   1
T    0  1   1   2

Answer: “CT” (length = 2)

The Pattern

// Create a table
let dp = Array(m+1).fill()
  .map(() => Array(n+1).fill(0));

// Fill it step by step
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (str1[i-1] === str2[j-1]) {
      dp[i][j] = dp[i-1][j-1] + 1;
    } else {
      dp[i][j] = Math.max(
        dp[i-1][j],
        dp[i][j-1]
      );
    }
  }
}

2. Edit Distance - The Word Transformer

The Story

You’re a text message editor. Your friend typed “KITTEN” but meant to type “SITTING”. How many button presses (edits) do you need?

Three magic powers:

1. Insert a letter
2. Delete a letter
3. Replace a letter

Step-by-Step Transformation

KITTEN → SITTEN  (replace K with S)
SITTEN → SITTIN  (replace E with I)
SITTIN → SITTING (insert G)

Answer: 3 edits!

How It Works

Think of a treasure map grid:

        ""  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

The code:

function editDistance(word1, word2) {
  let m = word1.length;
  let n = word2.length;

  // Create our game board
  let dp = Array(m + 1).fill()
    .map(() => Array(n + 1).fill(0));

  // First row: inserting letters
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }

  // First column: deleting letters
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }

  // Fill the board
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i-1] === word2[j-1]) {
        // Letters match! No edit needed
        dp[i][j] = dp[i-1][j-1];
      } else {
        // Pick the cheapest option
        dp[i][j] = 1 + Math.min(
          dp[i-1][j],     // delete
          dp[i][j-1],     // insert
          dp[i-1][j-1]    // replace
        );
      }
    }
  }

  return dp[m][n];
}

// Example
editDistance("kitten", "sitting"); // 3

Visual Flow

graph TD
    A["Start: kitten"] --> B{Letters match?}
    B -->|Yes| C["Keep it, move on"]
    B -->|No| D["Choose cheapest"]
    D --> E["Insert"]
    D --> F["Delete"]
    D --> G["Replace"]
    E --> H["Add 1 to cost"]
    F --> H
    G --> H
    H --> I["Continue to next"]
    I --> J["End: sitting"]

3. Word Break - The Sentence Splitter

The Story

Imagine you receive a text with no spaces:

“ilovedogs”

Can you split it into real words using a dictionary?

Dictionary: [“i”, “love”, “dogs”, “dog”, “sand”, “and”]

Answer: Yes! → “i love dogs”

How It Works

We check each position: “Can I reach here by splitting into valid words?”

String: "ilovedogs"
         i l o v e d o g s
         0 1 2 3 4 5 6 7 8

Position checks:
- Position 1: "i" in dictionary? YES!
- Position 5: "love" in dictionary? YES!
- Position 9: "dogs" in dictionary? YES!

The Code

function wordBreak(s, wordDict) {
  let words = new Set(wordDict);
  let n = s.length;

  // dp[i] = can we split s[0..i-1]?
  let dp = Array(n + 1).fill(false);
  dp[0] = true; // Empty string is valid

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      // Check: valid split at j AND
      // word from j to i exists?
      let word = s.slice(j, i);
      if (dp[j] && words.has(word)) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}

// Example
wordBreak("ilovedogs",
  ["i", "love", "dogs"]); // true

Visual Flow

graph TD
    A["ilovedogs"] --> B["Check: i"]
    B -->|Valid word| C["Check: love"]
    C -->|Valid word| D["Check: dogs"]
    D -->|Valid word| E["SUCCESS!"]

4. Wildcard Matching - The Fortune Teller

The Story

Imagine a fortune teller who can predict words with special cards:

• ? matches exactly ONE character (like a joker card)
• * matches ZERO or MORE characters (like a magic wand)

Example:

• Pattern: "c?t"
• Matches: “cat”, “cut”, “cot”
• Doesn’t match: “cart” (too long!)

Example with star:

• Pattern: "c*t"
• Matches: “cat”, “cart”, “carrot”, “ct”

How It Works

We build a matching table:

Pattern: "a*b"
String:  "axxb"

        ""  a   *   b
    ""   T  F   F   F
    a    F  T   T   F
    x    F  F   T   F
    x    F  F   T   F
    b    F  F   T   T

T = True (matches), F = False (no match)

The Code

function wildcardMatch(s, p) {
  let m = s.length;
  let n = p.length;

  let dp = Array(m + 1).fill()
    .map(() => Array(n + 1).fill(false));

  dp[0][0] = true; // Empty matches empty

  // Handle leading stars
  for (let j = 1; j <= n; j++) {
    if (p[j-1] === '*') {
      dp[0][j] = dp[0][j-1];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j-1] === '*') {
        // Star: match zero OR more
        dp[i][j] = dp[i][j-1] || // zero
                   dp[i-1][j];   // more
      } else if (p[j-1] === '?' ||
                 s[i-1] === p[j-1]) {
        // ? or exact match
        dp[i][j] = dp[i-1][j-1];
      }
    }
  }

  return dp[m][n];
}

// Examples
wildcardMatch("cat", "c?t");   // true
wildcardMatch("cart", "c*t");  // true
wildcardMatch("cat", "c*t*");  // true

Visual Flow

graph TD
    A["Pattern: c*t"] --> B{Current char?}
    B -->|Star *| C["Match 0 chars OR more"]
    B -->|Question ?| D["Match exactly 1 char"]
    B -->|Letter| E["Must match exactly"]
    C --> F["Continue checking"]
    D --> F
    E --> F
    F --> G["Final match result"]

5. Regular Expression Matching - The Ultimate Pattern Master

The Story

This is the most powerful spell! It has two magic symbols:

• . (dot) matches any SINGLE character
• * (star) matches ZERO or more of the PREVIOUS character

Important: The star is different here! It affects the character BEFORE it.

Examples:

• Pattern: "a*" → matches “”, “a”, “aa”, “aaa”…
• Pattern: ".*" → matches ANYTHING!
• Pattern: "a.b" → matches “aab”, “axb”, “a9b”

How It Works

The star creates two choices:

1. Use zero of the previous character (skip it)
2. Use one more of the previous character

function regexMatch(s, p) {
  let m = s.length;
  let n = p.length;

  let dp = Array(m + 1).fill()
    .map(() => Array(n + 1).fill(false));

  dp[0][0] = true;

  // Patterns like a*, a*b*, a*b*c* can
  // match empty string
  for (let j = 2; j <= n; j++) {
    if (p[j-1] === '*') {
      dp[0][j] = dp[0][j-2];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j-1] === '*') {
        // Star: affects previous char
        // Option 1: use zero (skip prev+*)
        dp[i][j] = dp[i][j-2];

        // Option 2: use one more
        // (if prev matches current)
        let prevP = p[j-2];
        if (prevP === '.' ||
            prevP === s[i-1]) {
          dp[i][j] = dp[i][j] ||
                     dp[i-1][j];
        }
      } else if (p[j-1] === '.' ||
                 p[j-1] === s[i-1]) {
        // Dot or exact match
        dp[i][j] = dp[i-1][j-1];
      }
    }
  }

  return dp[m][n];
}

// Examples
regexMatch("aa", "a*");     // true
regexMatch("ab", ".*");     // true
regexMatch("aab", "c*a*b"); // true
// (c* = zero c's, a* = two a's)

Key Difference: Wildcard vs Regex

Visual Flow

graph TD
    A["Pattern: a*b"] --> B{See star *?}
    B -->|Yes| C["Two choices"]
    C --> D[Skip: use zero a's]
    C --> E["Match: use one more a"]
    B -->|No| F["Match exactly"]
    D --> G["Check remaining"]
    E --> G
    F --> G
    G --> H["Final result"]

The Big Picture: Comparing All Four

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

    B --> F["Transform one word to another"]
    C --> G["Split into dictionary words"]
    D --> H["Match with * and ?"]
    E --> I["Match with . and *"]

Quick Reference Table

You Did It!

You’ve learned the four magical spells of String DP:

1. Edit Distance - The Word Transformer
2. Word Break - The Sentence Splitter
3. Wildcard Matching - The Fortune Teller
4. Regular Expression Matching - The Ultimate Pattern Master

Each one uses the same secret: Build a table, solve small problems, combine them into the big answer!

Now go practice these spells. Soon you’ll be a String DP wizard too!