Diff Between Two Strings Given two strings of uppercase letters source and target, list (in string form) a sequence of edits to convert from source to target that uses the least edits possible.
For example, with strings source = "ABCDEFG", and target = "ABDFFGH" we might return: ["A", "B", "-C", "D", "-E", "F", "+F", "G", "+H"
More formally, for each character C in source, we will either write the token C, which does not count as an edit; or write the token -C, which counts as an edit.
Additionally, between any token that we write, we may write +D where D is any letter, which counts as an edit.
At the end, when reading the tokens from left to right, and not including tokens prefixed with a minus-sign, the letters should spell out target (when ignoring plus-signs.)
In the example, the answer of A B -C D -E F +F G +H has total number of edits 4 (the minimum possible), and ignoring subtraction-tokens, spells out A, B, D, F, +F, G, +H which represents the string target.
If there are multiple answers, use the answer that favors removing from the source first.
I have written the following code
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int myfunc(const string& source,const string& target,int i,int j,vector<vector<int>>& dp){
if(i==source.size() || j==target.size()) return target.size()-j;
if(dp[i][j]!=-1) return dp[i][j];
if(source[i]==target[j]) return dp[i][j]=myfunc(source,target,i+1,j+1,dp);
return dp[i][j]=1+min(myfunc(source,target,i+1,j,dp),myfunc(source,target,i,j+1,dp));
}
vector<string> diffBetweenTwoStrings(const string& source,const string& target)
{
// your code goes here
int m=source.size();
int n=target.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
int x=myfunc(source,target,0,0,dp);
vector<string> result;
int i=0;
int j=0;
while(i<m && j<n){
if(source[i]==target[j]){
string storer="";
storer+=source[i];
result.push_back(storer);
i++;
j++;
}
else{
if(dp[i+1][j]<=dp[i][j+1]){
string storer="";
storer+=source[i];
result.push_back("-"+storer);
i++;
}
else{
string storer="";
storer+=target[j];
result.push_back("+"+storer);
j++;
}
}
}
while(j<n){
string storer="";
storer+=target[j];
result.push_back("+"+storer);
j++;
}
return result;
}
I know that I have to use dynamic programming followed by construction of the vector but I it is giving me incorrect result.this is the output I am getting Minimum edits: 10 Sequence of edits: A B -C D -E F -G +F +G +H but I need "A", "B", "-C", "D", "-E", "F", "+F", "G", "+H" I don't know where have I gone wrong?