# Evolve from brute force to dp

1. O(3^max(n1,n2)) We edit word 1 only and there are 3 operations
``````    int minDistance(string word1, string word2) {
return minDistance(0,0,word1,word2);
}
int minDistance(int p1, int p2, string &word1, string &word2) {
if(p1==word1.size()) return word2.size()-p2; //dist between a string and a empty string
if(p2==word2.size()) return word1.size()-p1;
if(word1[p1]==word2[p2]) return minDistance(p1+1,p2+1,word1,word2);
int ins = minDistance(p1,p2+1,word1,word2);
int del = minDistance(p1+1,p2,word1,word2);
int rpl = minDistance(p1+1,p2+1,word1,word2);
return min(ins,min(del,rpl))+1;
}
``````

2 O(n1n2) memorization

``````    int minDistance(string word1, string word2) {
vector<vector<int>> mem(word1.size(),vector<int>(word2.size(),-1));
return minDistance(0,0,word1,word2,mem);
}
int minDistance(int p1, int p2, string &word1, string &word2,vector<vector<int>>& mem) {
if(p1==word1.size()) return word2.size()-p2;
if(p2==word2.size()) return word1.size()-p1;
if(mem[p1][p2]>=0) return mem[p1][p2];
if(word1[p1]==word2[p2]) return mem[p1][p2]=minDistance(p1+1,p2+1,word1,word2,mem);
int ins = minDistance(p1,p2+1,word1,word2,mem);
int del = minDistance(p1+1,p2,word1,word2,mem);
int rpl = minDistance(p1+1,p2+1,word1,word2,mem);
return mem[p1][p2] = min(ins,min(del,rpl))+1;
}
``````

3 O(n1n2) dp

``````    int minDistance(string word1, string word2) {
int n1 = word1.size(),n2=word2.size();
vector<vector<int>> dp(n1+1,vector<int>(n2+1));
for(int i=0;i<n1;i++) dp[i][n2] = n1-i;
for(int j=0;j<n2;j++) dp[n1][j] = n2-j;
for(int i=n1-1;i>=0;i--)
for(int j=n2-1;j>=0;j--)
dp[i][j] = word1[i]==word2[j]? dp[i+1][j+1] : min(min(dp[i][j+1],dp[i+1][j]),dp[i+1][j+1])+1;
return dp[0][0];
}
``````

4 linear space dp

``````    int minDistance(string word1, string word2) {
int s1=word1.size(),s2=word2.size();
vector<int> dp(s1+1);
iota(dp.rbegin(),dp.rend(),0);
for(int i=s2-1;i>=0;i--) {
int i1j1 = dp[s1];
dp[s1] = s2-i;
for(int j=s1-1;j>=0;j--) {
int temp=dp[j];
dp[j]=min(dp[j+1]+1,min(dp[j]+1,i1j1+(word2[i]!=word1[j])));
i1j1=temp;
}
}
return dp[0];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.