Untitled
#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