Edit Distance (Levenshtein Distance) measures how different two strings are by counting the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into the other. The O(mn) DP solution fills a 2D table and is widely used in spell checkers, DNA alignment, and NLP.
int editDistance(string& a, string& b) {
int m=a.size(), n=b.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
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++)
dp[i][j]=a[i-1]==b[j-1] ? dp[i-1][j-1] : 1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
return dp[m][n];
}Insert: dp[i][j-1]+1 (insert b[j] after a[i]). Delete: dp[i-1][j]+1 (delete a[i]). Replace: dp[i-1][j-1]+1 (replace a[i] with b[j]). If a[i]==b[j], no operation needed: dp[i-1][j-1].
dp[i][0]=i: transforming prefix of a (length i) to empty string requires i deletions. dp[0][j]=j: transforming empty to prefix of b (length j) requires j insertions.
Edit distance powers: spell checkers (suggest nearest word), DNA alignment (measuring mutation distance), plagiarism detection, and autocomplete/search query suggestion.
Quiz coming soon for this algorithm.