Untitled

 avatar
unknown
plain_text
a year ago
747 B
1
Indexable
#define ll long long
class Solution {
public:
    ll solve(string &s1,string &s2,int i,int j,vector<vector<int>>&dp){
        if(i==s1.size() && j==s2.size()) return 0;
        if(i==s1.size() && j!=s2.size()) return s2.size()-j;
        if(i!=s1.size() && j==s2.size()) return s1.size()-i;
        
        if(dp[i][j]!=-1) return dp[i][j];
        if(s1[i]==s2[j]) return solve(s1,s2,i+1,j+1,dp);
        ll ins= solve(s1,s2,i,j+1,dp);
        ll del=solve(s1,s2,i+1,j,dp);
        ll rep=solve(s1,s2,i+1,j+1,dp);
        return dp[i][j]=1+min(ins,min(rep,del));
    }
    int minDistance(string s1, string s2) {
        vector<vector<int>>dp(s1.size(),vector<int>(s2.size(),-1));;
        return solve(s1,s2,0,0,dp);
    }
};
Leave a Comment