diff between 2 strings

Question

I am solving a problem on one of the online platforms where the question is on finding the diff between 2 string.

Question: 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"

Here is what I tried:

function diffBetweenTwoStrings(source, target) {
  console.log(source);
  console.log(target);
  let output = [],
    result = getCompareMap(source, target);

  buildTheResult(result, source, target);

  console.log(result);

  constructOutput(source, target, result, output)

  return output;
}

function buildTheResult(result, source, target) {
  for (let row = 0; row < target.length; row++) {
    for (let col = 0; col < source.length; col++) {
      if (source[col] === target[row]) {
        result[row + 1][col + 1] = result[row][col];
      } else {
        result[row + 1][col + 1] = Math.min(result[row + 1][col], result[row][col + 1]) + 1;
      }
    }
  }
}

function constructOutput(source, target, result, output) {
  let rows = target.length,
    cols = source.length;

  while (cols > 0 && rows > 0) {
    // console.log(`source: ${source[cols-1]} target: ${target[rows-1]} result col+1: ${result[rows][cols]} row+1: ${result[rows][cols]}`);
    if ((source[cols - 1] === target[rows - 1]) && ((result[rows - 1][cols - 1] <= result[rows - 1][cols]) && (result[rows - 1][cols - 1] <= result[rows][cols - 1]))) {
      //&& (result[rows - 1][cols - 1] <= result[rows - 1][cols])) {
      output.unshift(source[cols - 1]);
      // console.log("diagonal up with " + source[cols - 1]);
      rows--;
      cols--;
    } else if (result[rows - 1][cols] <= result[rows][cols - 1]) {
      output.unshift("+" + target[rows - 1]);
      // console.log("moving up with " + target[rows - 1]);
      rows--;
    } else if (result[rows][cols - 1] <= result[rows - 1][cols]) {
      output.unshift("-" + source[cols - 1]);
      // console.log("moving left with " + source[cols - 1]);
      cols--;
    }
  }

  while (rows > 0) {
    if (result[rows - 1][cols] <= result[rows][cols]) {
      output.unshift("+" + target[rows - 1]);
    } else {
      output.unshift(target[rows - 1]);
    }
    rows--;
  }

  while (cols > 0) {
    if (result[rows][cols - 1] <= result[rows][cols]) {
      output.unshift("-" + source[cols - 1]);
    } else {
      output.unshift(source[cols - 1]);
    }
    cols--;
  }
}

function getCompareMap(source, target) {
  let i, compareMap = [...Array(target.length + 1)].map(x => Array(source.length + 1).fill(0));

  for (i = 0; i <= target.length; i++) {
    compareMap[i][0] = i;
  }
  for (i = 0; i <= source.length; i++) {
    compareMap[0][i] = i;
  }

  return compareMap;
}

// O(n^2)
let source = 'GMMGZGGLUGUH',
  target = 'HPGPPMGLLUUU';

console.log(diffBetweenTwoStrings(source, target));

// expect => ["+H","+P","G","-M","+P","+P","M","G","-Z","-G","-G","L","+L","U","-G","U","-H","+U"]
// actual => ["+H","+P","G","+P","+P","M","-M","G","-Z","-G","-G","L","+L","U","-G","U","-H","+U" ]

It works for 6 cases and fails for 2(total 8 cases).

The other case it fails for is:

source = "AABACC"
target = "BABCAC"

// Expected => ["-A","-A","B","A","+B","C","+A","C"]
// Actual =>   ["+B","A","-A","B","+C","A","C","-C"]

What am I missing?

stackoverflow.com/questions/52162091/…

Dmitrii Bychenko
– Dmitrii Bychenko

2019-08-28 19:16:42 +00:00
Commented Aug 28, 2019 at 19:16 — Dmitrii Bychenko
– Dmitrii Bychenko, Commented Aug 28, 2019 at 19:16

NPE · Accepted Answer · 2019-08-28 18:07:11Z

2

If this is the original question, it includes the following proviso:

If there are multiple answers, use the answer that favors removing from the source first.

Your answer doesn't satisfy this criterion.

answered Aug 28, 2019 at 18:07

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Surya Over a year ago

This is it "If there are multiple answers, use the answer that favors removing from the source first." Thanks.

Prune · Accepted Answer · 2019-08-28 18:02:43Z

1

You're "missing" that your actual results are another valid difference. Both edit lists are 8 elements long, with four matches, two deletions, and two insertions. Unless there is some particular criterion that you haven't listed, the two answers are equally correct.

answered Aug 28, 2019 at 18:02

Prune

78k14 gold badges63 silver badges83 bronze badges

Collectives™ on Stack Overflow

diff between 2 strings

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related