Learn Edit Distance — Free DSA Tutorial

Edit Distance Idea

Edit distance measures how different two strings are by counting the fewest single-character insertions, deletions, and substitutions needed to turn one string into the other — the same idea spell-checkers use to suggest corrections.

Example: Edit Distance Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use");
	}
}

print("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use")

#include <stdio.h>
int main() {
	printf("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use");
	return 0;
}

DP State

dp[i][j] stores the edit distance between the first i characters of one string and the first j characters of the other, so the final answer sits in the bottom-right corner of the table once every prefix pair has been filled in.

Example: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[7][8] = {0};
	cout << "dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[7][8];
		System.out.println("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]");
	}
}

dp = [[0]*8 for _ in range(7)]
print("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]")

#include <stdio.h>
int main() {
	int dp[7][8] = {0};
	printf("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]");
	return 0;
}

Transition

When the current characters match, no edit is needed and the value carries over unchanged from the diagonal; when they differ, you take the cheapest of the three possible edits — insert, delete, or substitute — and add one to whichever neighboring value that edit corresponds to.

Example: Transition

#include <iostream>
using namespace std;
int main() {
	string s1 = "kitten", s2 = "sitting";
	int n = s1.size(), m = s2.size();
	int dp[7][8];
	for (int i = 0; i <= n; i++) dp[i][0] = i;
	for (int j = 0; j <= m; j++) dp[0][j] = j;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1] : 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
	cout << "Edit distance: " << dp[n][m];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String s1 = "kitten", s2 = "sitting";
		int n = s1.length(), m = s2.length();
		int[][] dp = new int[n+1][m+1];
		for (int i = 0; i <= n; i++) dp[i][0] = i;
		for (int j = 0; j <= m; j++) dp[0][j] = j;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				dp[i][j] = s1.charAt(i-1)==s2.charAt(j-1) ? dp[i-1][j-1] : 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
		System.out.println("Edit distance: " + dp[n][m]);
	}
}

s1, s2 = "kitten", "sitting"
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): dp[i][0] = i
for j in range(m+1): dp[0][j] = j
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = dp[i-1][j-1] if s1[i-1]==s2[j-1] else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
print("Edit distance:", dp[n][m])

#include <stdio.h>
#include <string.h>
int min3(int a, int b, int c) { int m = a<b?a:b; return m<c?m:c; }
int main() {
	char s1[] = "kitten", s2[] = "sitting";
	int n = strlen(s1), m = strlen(s2);
	int dp[7][8];
	for (int i = 0; i <= n; i++) dp[i][0] = i;
	for (int j = 0; j <= m; j++) dp[0][j] = j;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1] : 1 + min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
	printf("Edit distance: %d", dp[n][m]);
	return 0;
}

Insert and Delete

An insertion into one string lines up with moving to the cell above (using one more character of the target without consuming one from the source), while a deletion lines up with moving to the cell on the left — both simply add one edit to a slightly smaller subproblem.

Example: Insert and Delete

#include <iostream>
using namespace std;
int main() {
	cout << "Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])");
	}
}

print("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])")

#include <stdio.h>
int main() {
	printf("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])");
	return 0;
}

Practice

Beyond spell-checkers, edit distance underlies DNA sequence alignment, plagiarism detection, and the 'did you mean' suggestions search engines show when a query doesn't match anything exactly.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions");
	}
}

print("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions")

#include <stdio.h>
int main() {
	printf("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions");
	return 0;
}

Edit Distance

Edit Distance Idea

DP State

Transition

Insert and Delete

Practice

Chapter Quiz — Complete all 12 topics to unlock

Login to run this code