Edit Distance — Wagner-Fischer DP

Problem

Given two words, find minimum operations (insert, delete, replace) to convert word1 to word2.

Example: word1="horse", word2="ros" → 3

Approach — 2D DP

dp[i][j] = min ops to transform word1[:i] to word2[:j].

Base: dp[i][0]=i, dp[0][j]=j
Match: dp[i][j] = dp[i-1][j-1]
Mismatch: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Time: O(m*n) | Space: O(n)

Solutions

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n=len(word1),len(word2)
        prev=list(range(n+1))
        for i in range(1,m+1):
            curr=[i]+(  [0]*n)
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]: curr[j]=prev[j-1]
                else: curr[j]=1+min(prev[j],curr[j-1],prev[j-1])
            prev=curr
        return prev[n]

C++

class Solution {
public:
    int minDistance(string w1, string w2){
        int m=w1.size(),n=w2.size();
        vector<int> prev(n+1); iota(prev.begin(),prev.end(),0);
        for(int i=1;i<=m;i++){
            vector<int> curr(n+1); curr[0]=i;
            for(int j=1;j<=n;j++)
                curr[j]=w1[i-1]==w2[j-1]?prev[j-1]:1+min({prev[j],curr[j-1],prev[j-1]});
            prev=curr;
        }
        return prev[n];
    }
};

Java

class Solution {
    public int minDistance(String w1, String w2){
        int m=w1.length(),n=w2.length();
        int[] prev=new int[n+1];
        for(int j=0;j<=n;j++) prev[j]=j;
        for(int i=1;i<=m;i++){
            int[] curr=new int[n+1]; curr[0]=i;
            for(int j=1;j<=n;j++)
                curr[j]=w1.charAt(i-1)==w2.charAt(j-1)?prev[j-1]:1+Math.min(prev[j],Math.min(curr[j-1],prev[j-1]));
            prev=curr;
        }
        return prev[n];
    }
}

Complexity

Time: O(m*n) | Space: O(n)