samedi 15 juillet 2023

Difference Between Two Strings question in c++

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?

Aucun commentaire:

Enregistrer un commentaire