String DP — Edit Distance & Palindromes
Classic string DP: transform one string into another using min operations.
LC 72 (Edit Distance), LC 5 (Longest Palindromic Substring), LC 516 (Longest Palindromic Subsequence).
Edit Distance — 3 operations: insert, delete, replace.
If
Else:
dp[i][j] = min edits to convert A[0..i-1] → B[0..j-1]:- If
A[i-1] == B[j-1]:dp[i][j] = dp[i-1][j-1](no cost) - Else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
→ replace, delete, insert
dp[i][j] = LPS length of s[i..j]:If
s[i]==s[j]: dp[i][j] = dp[i+1][j-1] + 2Else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
Filled
Current
Sources
Match / Optimal
Controls
Time: O(m·n) | Space: O(m·n)
Steps
0 stepsPress Run to trace the algorithm one step at a time.