class Solution {
public:
int editDistance(string s, string t) {
// Code here
int n = s.length();
int m = t.length();
vector<vector<int>> vec(n+1, vector<int>(m+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i-1] == t[j-1]){
vec[i][j] = 1+vec[i-1][j-1];
}else{
vec[i][j] = max(vec[i-1][j], vec[i][j-1]);
}
}
}
int x=n, y=m;
vector<pair<int, int>> index;
string lcs;
while(x>0 && y>0){
if(s[x-1]==t[y-1]){
lcs += s[x-1];
x--; y--;
index.push_back({x, y});
}else{
if(vec[x][y-1]>vec[x-1][y]){
y--;
}else{
x--;
}
}
}
index.push_back({-1, -1});
reverse(index.begin(), index.end());
index.push_back({n, m});
int editDis=0;
for(int i=1; i<index.size(); i++){
// cout << index[i].first << " " << index[i].second << endl;
int s_prt = index[i].first-index[i-1].first;
int t_prt = index[i].second-index[i-1].second;
// cout << s_prt-1 << " " << t_prt-1 << endl;
editDis += abs(max(s_prt, t_prt)-1);
}
return editDis;
}
};
I was solving edit distance on gfg. I knew the dp solution but I thought of something different. I feel this must work but its not. So can we have a discussion on what wrong in my approach and can this be made better
I think this image would give you a better idea what I was thinking about.
