Edit Distance (Levenshtein Distance) Code Implementations
Complete Edit Distance (Levenshtein Distance) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Edit Distance (Levenshtein Distance) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Edit Distance (Levenshtein Distance) Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
class EditDistance {
public:
static int editDistance(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = std::min({
dp[i - 1][j] + 1, // Delete
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
});
}
}
}
return dp[m][n];
}
// Space-optimized version using 1D array
static int editDistanceOptimized(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
// Use the shorter string for the DP array
if (m < n) {
std::swap(word1, word2);
std::swap(m, n);
}
std::vector<int> dp(n + 1, 0);
// Initialize first row
for (int j = 0; j <= n; j++) {
dp[j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (word1[i - 1] == word2[j - 1]) {
dp[j] = prev;
} else {
dp[j] = std::min({
dp[j] + 1, // Delete
dp[j - 1] + 1, // Insert
prev + 1 // Replace
});
}
prev = temp;
}
}
return dp[n];
}
// Edit Distance with operation tracking
struct EditDistanceResult {
int distance;
std::string operations;
EditDistanceResult(int dist, const std::string& ops) : distance(dist), operations(ops) {}
};
static EditDistanceResult editDistanceWithOperations(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
std::vector<std::vector<std::string>> operations(m + 1, std::vector<std::string>(n + 1, ""));
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
operations[i][0] = std::string(i, 'D');
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
operations[0][j] = std::string(j, 'I');
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
operations[i][j] = operations[i - 1][j - 1] + "M"; // Match
} else {
int deleteCost = dp[i - 1][j] + 1;
int insertCost = dp[i][j - 1] + 1;
int replaceCost = dp[i - 1][j - 1] + 1;
if (deleteCost <= insertCost && deleteCost <= replaceCost) {
dp[i][j] = deleteCost;
operations[i][j] = operations[i - 1][j] + "D"; // Delete
} else if (insertCost <= replaceCost) {
dp[i][j] = insertCost;
operations[i][j] = operations[i][j - 1] + "I"; // Insert
} else {
dp[i][j] = replaceCost;
operations[i][j] = operations[i - 1][j - 1] + "R"; // Replace
}
}
}
}
return EditDistanceResult(dp[m][n], operations[m][n]);
}
// Edit Distance with memoization (top-down approach)
static int editDistanceMemo(const std::string& word1, const std::string& word2) {
std::unordered_map<std::string, int> memo;
return solveMemo(word1, word2, word1.length(), word2.length(), memo);
}
private:
static int solveMemo(const std::string& word1, const std::string& word2,
int i, int j, std::unordered_map<std::string, int>& memo) {
if (i == 0) return j;
if (j == 0) return i;
std::string key = std::to_string(i) + "," + std::to_string(j);
if (memo.find(key) != memo.end()) return memo[key];
int result;
if (word1[i - 1] == word2[j - 1]) {
result = solveMemo(word1, word2, i - 1, j - 1, memo);
} else {
result = std::min({
solveMemo(word1, word2, i - 1, j, memo) + 1, // Delete
solveMemo(word1, word2, i, j - 1, memo) + 1, // Insert
solveMemo(word1, word2, i - 1, j - 1, memo) + 1 // Replace
});
}
memo[key] = result;
return result;
}
public:
// Weighted Edit Distance (different costs for different operations)
static int weightedEditDistance(const std::string& word1, const std::string& word2,
int insertCost, int deleteCost, int replaceCost) {
int m = word1.length();
int n = word2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i * deleteCost;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j * insertCost;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = std::min({
dp[i - 1][j] + deleteCost, // Delete
dp[i][j - 1] + insertCost, // Insert
dp[i - 1][j - 1] + replaceCost // Replace
});
}
}
}
return dp[m][n];
}
// Damerau-Levenshtein Distance (includes transposition)
static int damerauLevenshteinDistance(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = std::min({
dp[i - 1][j] + 1, // Delete
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
});
// Add transposition cost
if (i > 1 && j > 1 &&
word1[i - 1] == word2[j - 2] &&
word1[i - 2] == word2[j - 1]) {
dp[i][j] = std::min(dp[i][j], dp[i - 2][j - 2] + 1);
}
}
}
}
return dp[m][n];
}
};JAVA Implementation
// Edit Distance (Levenshtein Distance) Implementation in Java
public class EditDistance {
public static int editDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
Math.min(dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1) // Replace
);
}
}
}
return dp[m][n];
}
// Space-optimized version using 1D array
public static int editDistanceOptimized(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// Use the shorter string for the DP array
if (m < n) {
String temp = word1;
word1 = word2;
word2 = temp;
int tempLen = m;
m = n;
n = tempLen;
}
int[] dp = new int[n + 1];
// Initialize first row
for (int j = 0; j <= n; j++) {
dp[j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = prev;
} else {
dp[j] = Math.min(
dp[j] + 1, // Delete
Math.min(dp[j - 1] + 1, // Insert
prev + 1) // Replace
);
}
prev = temp;
}
}
return dp[n];
}
// Edit Distance with operation tracking
public static class EditDistanceResult {
public int distance;
public String operations;
public EditDistanceResult(int distance, String operations) {
this.distance = distance;
this.operations = operations;
}
}
public static EditDistanceResult editDistanceWithOperations(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
String[][] operations = new String[m + 1][n + 1];
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
operations[i][0] = "D".repeat(i);
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
operations[0][j] = "I".repeat(j);
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
operations[i][j] = operations[i - 1][j - 1] + "M"; // Match
} else {
int deleteCost = dp[i - 1][j] + 1;
int insertCost = dp[i][j - 1] + 1;
int replaceCost = dp[i - 1][j - 1] + 1;
if (deleteCost <= insertCost && deleteCost <= replaceCost) {
dp[i][j] = deleteCost;
operations[i][j] = operations[i - 1][j] + "D"; // Delete
} else if (insertCost <= replaceCost) {
dp[i][j] = insertCost;
operations[i][j] = operations[i][j - 1] + "I"; // Insert
} else {
dp[i][j] = replaceCost;
operations[i][j] = operations[i - 1][j - 1] + "R"; // Replace
}
}
}
}
return new EditDistanceResult(dp[m][n], operations[m][n]);
}
// Edit Distance with memoization (top-down approach)
public static int editDistanceMemo(String word1, String word2) {
java.util.Map<String, Integer> memo = new java.util.HashMap<>();
return solveMemo(word1, word2, word1.length(), word2.length(), memo);
}
private static int solveMemo(String word1, String word2, int i, int j, java.util.Map<String, Integer> memo) {
if (i == 0) return j;
if (j == 0) return i;
String key = i + "," + j;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
result = solveMemo(word1, word2, i - 1, j - 1, memo);
} else {
result = Math.min(
solveMemo(word1, word2, i - 1, j, memo) + 1, // Delete
Math.min(solveMemo(word1, word2, i, j - 1, memo) + 1, // Insert
solveMemo(word1, word2, i - 1, j - 1, memo) + 1) // Replace
);
}
memo.put(key, result);
return result;
}
// Weighted Edit Distance (different costs for different operations)
public static int weightedEditDistance(String word1, String word2, int insertCost, int deleteCost, int replaceCost) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i * deleteCost;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j * insertCost;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + deleteCost, // Delete
Math.min(dp[i][j - 1] + insertCost, // Insert
dp[i - 1][j - 1] + replaceCost) // Replace
);
}
}
}
return dp[m][n];
}
// Damerau-Levenshtein Distance (includes transposition)
public static int damerauLevenshteinDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
Math.min(dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1) // Replace
);
// Add transposition cost
if (i > 1 && j > 1 &&
word1.charAt(i - 1) == word2.charAt(j - 2) &&
word1.charAt(i - 2) == word2.charAt(j - 1)) {
dp[i][j] = Math.min(dp[i][j], dp[i - 2][j - 2] + 1);
}
}
}
}
return dp[m][n];
}
}JAVASCRIPT Implementation
// Edit Distance (Levenshtein Distance) Implementation in JavaScript
function editDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
// Initialize first row and column
for (let i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
);
}
}
}
return dp[m][n];
}
// Space-optimized version using 1D array
function editDistanceOptimized(word1, word2) {
const m = word1.length;
const n = word2.length;
// Use the shorter string for the DP array
if (m < n) {
[word1, word2] = [word2, word1];
[m, n] = [n, m];
}
const dp = Array(n + 1).fill(0);
// Initialize first row
for (let j = 0; j <= n; j++) {
dp[j] = j;
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
let prev = dp[0];
dp[0] = i;
for (let j = 1; j <= n; j++) {
const temp = dp[j];
if (word1[i - 1] === word2[j - 1]) {
dp[j] = prev;
} else {
dp[j] = Math.min(
dp[j] + 1, // Delete
dp[j - 1] + 1, // Insert
prev + 1 // Replace
);
}
prev = temp;
}
}
return dp[n];
}
// Edit Distance with operation tracking
function editDistanceWithOperations(word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
const operations = Array(m + 1).fill().map(() => Array(n + 1).fill(''));
// Initialize first row and column
for (let i = 0; i <= m; i++) {
dp[i][0] = i;
operations[i][0] = 'D'.repeat(i);
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j;
operations[0][j] = 'I'.repeat(j);
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
operations[i][j] = operations[i - 1][j - 1] + 'M'; // Match
} else {
const deleteCost = dp[i - 1][j] + 1;
const insertCost = dp[i][j - 1] + 1;
const replaceCost = dp[i - 1][j - 1] + 1;
if (deleteCost <= insertCost && deleteCost <= replaceCost) {
dp[i][j] = deleteCost;
operations[i][j] = operations[i - 1][j] + 'D'; // Delete
} else if (insertCost <= replaceCost) {
dp[i][j] = insertCost;
operations[i][j] = operations[i][j - 1] + 'I'; // Insert
} else {
dp[i][j] = replaceCost;
operations[i][j] = operations[i - 1][j - 1] + 'R'; // Replace
}
}
}
}
return {
distance: dp[m][n],
operations: operations[m][n]
};
}
// Edit Distance with detailed transformation steps
function editDistanceWithSteps(word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
const steps = Array(m + 1).fill().map(() => Array(n + 1).fill(null));
// Initialize first row and column
for (let i = 0; i <= m; i++) {
dp[i][0] = i;
steps[i][0] = { type: 'delete', char: word1[i - 1] || '', cost: 1 };
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j;
steps[0][j] = { type: 'insert', char: word2[j - 1] || '', cost: 1 };
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
steps[i][j] = { type: 'match', char: word1[i - 1], cost: 0 };
} else {
const deleteCost = dp[i - 1][j] + 1;
const insertCost = dp[i][j - 1] + 1;
const replaceCost = dp[i - 1][j - 1] + 1;
if (deleteCost <= insertCost && deleteCost <= replaceCost) {
dp[i][j] = deleteCost;
steps[i][j] = { type: 'delete', char: word1[i - 1], cost: 1 };
} else if (insertCost <= replaceCost) {
dp[i][j] = insertCost;
steps[i][j] = { type: 'insert', char: word2[j - 1], cost: 1 };
} else {
dp[i][j] = replaceCost;
steps[i][j] = { type: 'replace', char: word2[j - 1], cost: 1 };
}
}
}
}
// Reconstruct the transformation steps
const transformationSteps = [];
let i = m, j = n;
while (i > 0 || j > 0) {
const step = steps[i][j];
transformationSteps.unshift(step);
if (step.type === 'match' || step.type === 'replace') {
i--;
j--;
} else if (step.type === 'delete') {
i--;
} else if (step.type === 'insert') {
j--;
}
}
return {
distance: dp[m][n],
steps: transformationSteps
};
}
// Edit Distance with memoization (top-down approach)
function editDistanceMemo(word1, word2) {
const memo = new Map();
function solve(i, j) {
if (i === 0) return j;
if (j === 0) return i;
const key = i + ',' + j;
if (memo.has(key)) return memo.get(key);
let result;
if (word1[i - 1] === word2[j - 1]) {
result = solve(i - 1, j - 1);
} else {
result = Math.min(
solve(i - 1, j) + 1, // Delete
solve(i, j - 1) + 1, // Insert
solve(i - 1, j - 1) + 1 // Replace
);
}
memo.set(key, result);
return result;
}
return solve(word1.length, word2.length);
}
// Weighted Edit Distance (different costs for different operations)
function weightedEditDistance(word1, word2, costs = { insert: 1, delete: 1, replace: 1 }) {
const m = word1.length;
const n = word2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
// Initialize first row and column
for (let i = 0; i <= m; i++) {
dp[i][0] = i * costs.delete;
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j * costs.insert;
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + costs.delete, // Delete
dp[i][j - 1] + costs.insert, // Insert
dp[i - 1][j - 1] + costs.replace // Replace
);
}
}
}
return dp[m][n];
}PYTHON Implementation
# Edit Distance (Levenshtein Distance) Implementation in Python
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # Delete
dp[i][j - 1] + 1, # Insert
dp[i - 1][j - 1] + 1 # Replace
)
return dp[m][n]
# Space-optimized version using 1D array
def edit_distance_optimized(word1, word2):
m, n = len(word1), len(word2)
# Use the shorter string for the DP array
if m < n:
word1, word2 = word2, word1
m, n = n, m
dp = [0] * (n + 1)
# Initialize first row
for j in range(n + 1):
dp[j] = j
# Fill the DP table
for i in range(1, m + 1):
prev = dp[0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i - 1] == word2[j - 1]:
dp[j] = prev
else:
dp[j] = min(
dp[j] + 1, # Delete
dp[j - 1] + 1, # Insert
prev + 1 # Replace
)
prev = temp
return dp[n]
# Edit Distance with operation tracking
def edit_distance_with_operations(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
operations = [[''] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(m + 1):
dp[i][0] = i
operations[i][0] = 'D' * i
for j in range(n + 1):
dp[0][j] = j
operations[0][j] = 'I' * j
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
operations[i][j] = operations[i - 1][j - 1] + 'M' # Match
else:
delete_cost = dp[i - 1][j] + 1
insert_cost = dp[i][j - 1] + 1
replace_cost = dp[i - 1][j - 1] + 1
if delete_cost <= insert_cost and delete_cost <= replace_cost:
dp[i][j] = delete_cost
operations[i][j] = operations[i - 1][j] + 'D' # Delete
elif insert_cost <= replace_cost:
dp[i][j] = insert_cost
operations[i][j] = operations[i][j - 1] + 'I' # Insert
else:
dp[i][j] = replace_cost
operations[i][j] = operations[i - 1][j - 1] + 'R' # Replace
return {
'distance': dp[m][n],
'operations': operations[m][n]
}
# Edit Distance with detailed transformation steps
def edit_distance_with_steps(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
steps = [[None] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(m + 1):
dp[i][0] = i
steps[i][0] = {'type': 'delete', 'char': word1[i - 1] if i > 0 else '', 'cost': 1}
for j in range(n + 1):
dp[0][j] = j
steps[0][j] = {'type': 'insert', 'char': word2[j - 1] if j > 0 else '', 'cost': 1}
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
steps[i][j] = {'type': 'match', 'char': word1[i - 1], 'cost': 0}
else:
delete_cost = dp[i - 1][j] + 1
insert_cost = dp[i][j - 1] + 1
replace_cost = dp[i - 1][j - 1] + 1
if delete_cost <= insert_cost and delete_cost <= replace_cost:
dp[i][j] = delete_cost
steps[i][j] = {'type': 'delete', 'char': word1[i - 1], 'cost': 1}
elif insert_cost <= replace_cost:
dp[i][j] = insert_cost
steps[i][j] = {'type': 'insert', 'char': word2[j - 1], 'cost': 1}
else:
dp[i][j] = replace_cost
steps[i][j] = {'type': 'replace', 'char': word2[j - 1], 'cost': 1}
# Reconstruct the transformation steps
transformation_steps = []
i, j = m, n
while i > 0 or j > 0:
step = steps[i][j]
transformation_steps.insert(0, step)
if step['type'] in ['match', 'replace']:
i -= 1
j -= 1
elif step['type'] == 'delete':
i -= 1
elif step['type'] == 'insert':
j -= 1
return {
'distance': dp[m][n],
'steps': transformation_steps
}
# Edit Distance with memoization (top-down approach)
def edit_distance_memo(word1, word2):
memo = {}
def solve(i, j):
if i == 0:
return j
if j == 0:
return i
if (i, j) in memo:
return memo[(i, j)]
if word1[i - 1] == word2[j - 1]:
result = solve(i - 1, j - 1)
else:
result = min(
solve(i - 1, j) + 1, # Delete
solve(i, j - 1) + 1, # Insert
solve(i - 1, j - 1) + 1 # Replace
)
memo[(i, j)] = result
return result
return solve(len(word1), len(word2))
# Weighted Edit Distance (different costs for different operations)
def weighted_edit_distance(word1, word2, costs={'insert': 1, 'delete': 1, 'replace': 1}):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(m + 1):
dp[i][0] = i * costs['delete']
for j in range(n + 1):
dp[0][j] = j * costs['insert']
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + costs['delete'], # Delete
dp[i][j - 1] + costs['insert'], # Insert
dp[i - 1][j - 1] + costs['replace'] # Replace
)
return dp[m][n]
# Damerau-Levenshtein Distance (includes transposition)
def damerau_levenshtein_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # Delete
dp[i][j - 1] + 1, # Insert
dp[i - 1][j - 1] + 1 # Replace
)
# Add transposition cost
if (i > 1 and j > 1 and
word1[i - 1] == word2[j - 2] and
word1[i - 2] == word2[j - 1]):
dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1)
return dp[m][n]