What signals in a problem statement indicate the Edit distance / matching sub-pattern?

"minimum operations to convert"; "delete characters with the smallest ASCII sum"; "wildcard", "regular expression", `*`, `?`, `.`; "interleaving"

Edit distance / matching (DP — Strings Sub-pattern)

Each cell picks the cheapest operation (insert / delete / replace), or for patterns decides true / false with the rule for ?, * or ..

Signals in the problem statement

›
"minimum operations to convert"
›
"delete characters with the smallest ASCII sum"
›
"wildcard", "regular expression", *, ?, .
›
"interleaving"

What makes it different

The base row / column carry real meaning (cost of building from nothing, or which pattern prefixes match an empty string). * in wildcards = any run; * in regex = zero or more of the previous character.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Edit Distance
Basic Anchor·LeetCode #72
WalkthroughMedium
2
Minimum ASCII Delete Sum for Two Strings
Basic Reinforcement·LeetCode #712
WalkthroughMedium
3
Interleaving String
Slight Variation·LeetCode #97
WalkthroughMedium
4
Wildcard Matching
Interview-Level·LeetCode #44
WalkthroughHard
5
Regular Expression Matching
Tricky / Edge Case·LeetCode #10
WalkthroughHard

Template

edit-distance-template.cpp

// Edit distance in one row: fewest insert / delete / replace to turn a into b.
int editDistance(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<int> dp(m + 1);
    for (int j = 0; j <= m; j++) dp[j] = j;          // "" -> b[0..j): j inserts
    for (int i = 1; i <= n; i++) {
        int diag = dp[0];                            // dp[i - 1][0]
        dp[0] = i;                                   // a[0..i) -> "": i deletes
        for (int j = 1; j <= m; j++) {
            int top = dp[j];                         // dp[i - 1][j]
            if (a[i - 1] == b[j - 1]) dp[j] = diag;  // last chars match: free
            else dp[j] = 1 + min({top,               // delete a[i - 1]
                                  dp[j - 1],         // insert b[j - 1]
                                  diag});            // replace
            diag = top;
        }
    }
    return dp[m];
}

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Longest common subsequence Common substring