AntInLoop

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]