String DP — Edit Distance, LCS, and Interleaving

def minDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = list(range(n+1))
    for i in range(1, m+1):
        prev = dp[:]
        dp[0] = i
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[j] = prev[j-1]
            else:
                dp[j] = 1 + min(prev[j], dp[j-1], prev[j-1])
    return dp[n]

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m+n != len(s3): return False
    dp = [False]*(n+1)
    dp[0] = True
    for j in range(1, n+1): dp[j] = dp[j-1] and s2[j-1]==s3[j-1]
    for i in range(1, m+1):
        dp[0] = dp[0] and s1[i-1] == s3[i-1]
        for j in range(1, n+1):
            dp[j] = (dp[j] and s1[i-1]==s3[i+j-1]) or (dp[j-1] and s2[j-1]==s3[i+j-1])
    return dp[n]

function minDistance(s1,s2){
    const m=s1.length,n=s2.length; let dp=Array.from({length:n+1},(_,j)=>j);
    for(let i=1;i<=m;i++){const prev=[...dp];dp[0]=i;for(let j=1;j<=n;j++)dp[j]=s1[i-1]===s2[j-1]?prev[j-1]:1+Math.min(prev[j],dp[j-1],prev[j-1]);}
    return dp[n];
}
function lcs(s1,s2){
    const m=s1.length,n=s2.length,dp=Array.from({length:m+1},()=>new Array(n+1).fill(0));
    for(let i=1;i<=m;i++)for(let j=1;j<=n;j++)dp[i][j]=s1[i-1]===s2[j-1]?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}

public int minDistance(String s1,String s2){
    int m=s1.length(),n=s2.length(); int[]dp=new int[n+1]; for(int j=0;j<=n;j++)dp[j]=j;
    for(int i=1;i<=m;i++){int[]prev=dp.clone();dp[0]=i;for(int j=1;j<=n;j++)dp[j]=s1.charAt(i-1)==s2.charAt(j-1)?prev[j-1]:1+Math.min(prev[j],Math.min(dp[j-1],prev[j-1]));}
    return dp[n];
}

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int minDistance(string s1,string s2){
    int m=s1.size(),n=s2.size(); vector<int>dp(n+1); iota(dp.begin(),dp.end(),0);
    for(int i=1;i<=m;i++){vector<int>prev=dp;dp[0]=i;for(int j=1;j<=n;j++)dp[j]=s1[i-1]==s2[j-1]?prev[j-1]:1+min({prev[j],dp[j-1],prev[j-1]});}
    return dp[n];
}

int editDist(char*s1,char*s2,int m,int n){int dp[n+1];for(int j=0;j<=n;j++)dp[j]=j;for(int i=1;i<=m;i++){int prev=dp[0];dp[0]=i;for(int j=1;j<=n;j++){int tmp=dp[j];dp[j]=s1[i-1]==s2[j-1]?prev:1+(dp[j]<dp[j-1]?(dp[j]<prev?dp[j]:prev):(dp[j-1]<prev?dp[j-1]:prev));prev=tmp;}}return dp[n];}