Difference Between Two Strings question in c++

Question

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?

Answer 1

if(i==source.size() || j==target.size()) return target.size()-j;

First, you forgot to assign the result to dp[i][j] in this case. It is needed because you analyze the DP array after you have computed the difference, so it better contain correct values.

Second, the case is just not correct. If you come to the end of the source string, you need to add all the remaining characters of the target. If you come to the end of the target string, you need to remove all the remaining characters of the source. It is fully symmetrical.

if (i == source.size())
  return dp[i][j] = target.size() - j;
if (j == target.size())
  return dp[i][j] = source.size() - i;