在JavaScript中查找两个字符串之间的不同

Question

我需要找到两个字符串之间的差异。

const string1 = 'lebronjames';
const string2 = 'lebronnjames';

期望的输出是找到额外的n并将其记录到控制台。

在JavaScript中有没有实现这个功能的方法？

- Elvis S.

---

还有 b 吗？ - Aziz.G

你能澄清一下你期望的输出吗？你只是想找到第一个不同的字符吗？还是需要找到所有不同的字符？如果是所有的话，第一个之后的字符使用什么样的阈值？ - Brad

你应该考虑计算编辑距离：https://zh.wikipedia.org/wiki/编辑距离 - slider

这个操作比你想象的要复杂得多。你的算法怎么知道第一个n之后的任何子字符串都应该进行比较呢？从严格的字母:字母的角度来看，整个字符串的下半部分都是不同的。 - isherwood

如果你在浏览器中搜索“字符串差异算法”，你会找到比我们在这里能解释得更好的参考资料。 - Prune

Answer 1

另一种更复杂的差异检查选项是使用PatienceDiff算法。我将此算法移植到了Javascript中，可以在以下网址找到：https://github.com/jonTrent/PatienceDiff。虽然该算法通常用于逐行比较文本（例如计算机程序），但仍可用于逐字符比较。例如，要比较两个字符串，可以执行以下操作...

let a = "thelebronnjamist";
let b = "the lebron james";

let difference = patienceDiff( a.split(""), b.split("") );

...使用difference.lines，将其设置为一个数组，其中包含比较的结果...

difference.lines: Array(19)

0: {line: "t", aIndex: 0, bIndex: 0}
1: {line: "h", aIndex: 1, bIndex: 1}
2: {line: "e", aIndex: 2, bIndex: 2}
3: {line: " ", aIndex: -1, bIndex: 3}
4: {line: "l", aIndex: 3, bIndex: 4}
5: {line: "e", aIndex: 4, bIndex: 5}
6: {line: "b", aIndex: 5, bIndex: 6}
7: {line: "r", aIndex: 6, bIndex: 7}
8: {line: "o", aIndex: 7, bIndex: 8}
9: {line: "n", aIndex: 8, bIndex: 9}
10: {line: "n", aIndex: 9, bIndex: -1}
11: {line: " ", aIndex: -1, bIndex: 10}
12: {line: "j", aIndex: 10, bIndex: 11}
13: {line: "a", aIndex: 11, bIndex: 12}
14: {line: "m", aIndex: 12, bIndex: 13}
15: {line: "i", aIndex: 13, bIndex: -1}
16: {line: "e", aIndex: -1, bIndex: 14}
17: {line: "s", aIndex: 14, bIndex: 15}
18: {line: "t", aIndex: 15, bIndex: -1}

无论是 aIndex === -1 还是 bIndex === -1，都表示两个字符串之间存在差异。具体来说...

• 第3个元素表示字符“ ”在b中的位置是3。
• 第10个元素表示字符“n”在a中的位置是9。
• 第11个元素表示字符“ ”在b中的位置是10。
• 第15个元素表示字符“i”在a中的位置是13。
• 第16个元素表示字符“e”在b中的位置是14。
• 第18个元素表示字符“t”在a中的位置是15。

请注意，PatienceDiff算法适用于比较两个相似的文本块或字符串。它不会告诉您是否发生了基本编辑。例如，以下内容...

let a = "james lebron";
let b = "lebron james";

let difference = patienceDiff( a.split(""), b.split("") );

返回包含difference.lines的内容...

difference.lines: Array(18)

0: {line: "j", aIndex: 0, bIndex: -1}
1: {line: "a", aIndex: 1, bIndex: -1}
2: {line: "m", aIndex: 2, bIndex: -1}
3: {line: "e", aIndex: 3, bIndex: -1}
4: {line: "s", aIndex: 4, bIndex: -1}
5: {line: " ", aIndex: 5, bIndex: -1}
6: {line: "l", aIndex: 6, bIndex: 0}
7: {line: "e", aIndex: 7, bIndex: 1}
8: {line: "b", aIndex: 8, bIndex: 2}
9: {line: "r", aIndex: 9, bIndex: 3}
10: {line: "o", aIndex: 10, bIndex: 4}
11: {line: "n", aIndex: 11, bIndex: 5}
12: {line: " ", aIndex: -1, bIndex: 6}
13: {line: "j", aIndex: -1, bIndex: 7}
14: {line: "a", aIndex: -1, bIndex: 8}
15: {line: "m", aIndex: -1, bIndex: 9}
16: {line: "e", aIndex: -1, bIndex: 10}
17: {line: "s", aIndex: -1, bIndex: 11}

请注意，PatienceDiff没有报告第一个和最后一个名称的交换，而是提供了一个结果，展示了从a中删除了哪些字符，b中添加了哪些字符以得到b的结果。

编辑：添加了新的算法，命名为patienceDiffPlus。

在思考以上提供的最后一个示例时，该示例显示了PatienceDiff在识别可能移动的行方面存在限制。我想到了一种巧妙地使用PatienceDiff算法来确定是否确实已经有任何行发生了移动而不仅仅显示删除和添加的方式。

简而言之，我在PatienceDiff.js文件底部添加了patienceDiffPlus算法（GitHub库已标识）。patienceDiffPlus算法将初步patienceDiff算法中删除的aLines[]和添加的bLines[]进行再次运行。即patienceDiffPlus正在寻找可能移动的行的最长公共子序列，并记录在原始的patienceDiff结果中。patienceDiffPlus算法继续进行此操作，直到不再发现任何移动的行。

现在，使用patienceDiffPlus，以下比较...

let a = "james lebron";
let b = "lebron james";

let difference = patienceDiffPlus( a.split(""), b.split("") );

...返回包含difference.lines的内容...

difference.lines: Array(18)

0: {line: "j", aIndex: 0, bIndex: -1, moved: true}
1: {line: "a", aIndex: 1, bIndex: -1, moved: true}
2: {line: "m", aIndex: 2, bIndex: -1, moved: true}
3: {line: "e", aIndex: 3, bIndex: -1, moved: true}
4: {line: "s", aIndex: 4, bIndex: -1, moved: true}
5: {line: " ", aIndex: 5, bIndex: -1, moved: true}
6: {line: "l", aIndex: 6, bIndex: 0}
7: {line: "e", aIndex: 7, bIndex: 1}
8: {line: "b", aIndex: 8, bIndex: 2}
9: {line: "r", aIndex: 9, bIndex: 3}
10: {line: "o", aIndex: 10, bIndex: 4}
11: {line: "n", aIndex: 11, bIndex: 5}
12: {line: " ", aIndex: 5, bIndex: 6, moved: true}
13: {line: "j", aIndex: 0, bIndex: 7, moved: true}
14: {line: "a", aIndex: 1, bIndex: 8, moved: true}
15: {line: "m", aIndex: 2, bIndex: 9, moved: true}
16: {line: "e", aIndex: 3, bIndex: 10, moved: true}
17: {line: "s", aIndex: 4, bIndex: 11, moved: true}

注意添加了moved属性，该属性标识一行（或字符）是否可能被移动。同样地，patienceDiffPlus只是匹配了删除的aLines[]和添加的bLines[]，因此不能保证这些行实际上被移动了，但很有可能它们确实被移动了。

- Trentium

---

太棒了，感谢与我们分享，这真正解决了一个问题！ - Elvis S.

我意识到可以优雅地利用patienceDiff算法来识别可能移动的行/字符，而不仅仅是识别删除和添加。我已经在我的原始答案中附加了一个编辑，其中包含新的patienceDiffPlus算法，并更新了我的GitHub存储库。 - Trentium

请使用带有空格的.split(' ')来标记单词，而不是字母。我们发现在突出显示长段落文本之间的差异时，这非常有用。感谢这个解决方案！ - Jan Werkhoven

Answer 2

这将返回两个字符串之间的第一个不同之处。

例如对于 lebronjames 和 lebronnjames，结果为 n。

const string1 = 'lebronjames';
const string2 = 'lebronnjabes';


const findFirstDiff = (str1, str2) =>
  str2[[...str1].findIndex((el, index) => el !== str2[index])];


// equivalent of 

const findFirstDiff2 = function(str1, str2) {
  return str2[[...str1].findIndex(function(el, index) {
    return el !== str2[index]
  })];
}



console.log(findFirstDiff2(string1, string2));
console.log(findFirstDiff(string1, string2));

- Aziz.G

---

虽然它不能找到所有的差异，但它会找到第一个差异，我能够用更多的代码来完成那部分 :D你能向我们解释一下你的代码吗？（给新手） - Elvis S.

不，你不是。我只是使用了 findIndex 来查找两个单词之间的第一个差异，然后使用索引 string[index]。使用 esc6 语法，代码看起来更简洁。 - Aziz.G

谢谢您的时间！我正在循环遍历string1和string2中的每个字符，然后进行比较。这很有效，但是我希望能够找到完整的不同字符序列，现在我找到了更好的方法并学习了一些扩展操作符。谢谢！ - Elvis S.

这并没有解决一种边缘情况，即更改是第一个字符串末尾的新字符。 - hash

findFirstDiff 当其中一个字符串为空时，无法正常工作。 - undefined

Answer 3

    function getDifference(a, b)
    {
        var i = 0;
        var j = 0;
        var result = "";

        while (j < b.length)
        {
         if (a[i] != b[j] || i == a.length)
             result += b[j];
         else
             i++;
         j++;
        }
        return result;
    }
    console.log(getDifference("lebronjames", "lebronnjames"));

- Nero

---

复制粘贴上一个主题的答案，但是这并不起作用，伙计.. :'( - Elvis S.

Answer 4

想要返回两个字符串之间的第一个不同之处，可以像这样进行调整：

排序和查找

const getDifference = (s, t) => {
  s = [...s].sort();
  t = [...t].sort();
  return t.find((char, i) => char !== s[i]);
};

console.log(getDifference('lebronjames', 'lebronnjames'));
console.log(getDifference('abc', 'abcd'));

添加字符代码

const getDifference = (s, t) => {
  let sum = t.charCodeAt(t.length - 1);
  for (let j = 0; j < s.length; j++) {
    sum -= s.charCodeAt(j);
    sum += t.charCodeAt(j);
  }
  return String.fromCharCode(sum);
};

console.log(getDifference('lebronjames', 'lebronnjames'));
console.log(getDifference('abc', 'abcd'));

- Penny Liu

Answer 5

var findTheDifference = function(s, t) {
  let res = [...s].sort();
  let res1 = [...t].sort();
  let j = 0;
  while (j < res1.length) {
    if (res[j] != res1[j]) {
      return res1[j];
    }
    j++;
  }
};

console.log(findTheDifference("a", "aa"))

- Md.Samiul Bashar

Answer 6

function findDifference(s, t) {

  if(s === '') return t;

  
  
  // this is useless and can be omitted.
  for(let i = 0; i < t.length; i++) {
    if(!s.split('').includes(t[i])) {
      return t[i];
    }
  }
  // this is useless and can be omitted.


  
  // (if the additional letter exists)
  // cache them, count values, different values of the same letter would give the answer.

  const obj_S = {};
  const obj_T = {};

  for(let i = 0; i < s.length; i++) {
    if(!obj_S[s[i]]) {
      obj_S[s[i]] = 1;
    }else {
      obj_S[s[i]]++;
    }
  }
  
  for(let i = 0; i < t.length; i++) {
    if(!obj_T[t[i]]) {
      obj_T[t[i]] = 1;
    }else {
      obj_T[t[i]]++;
    }
  }

  for(const key in obj_T) {
    if(obj_T[key] !== obj_S[key]) {
      return key
    }
  }

}

// if more than 1 letter -> store the values and the return, logic stays the same.

console.log(findDifference('john', 'johny')) // --> y
console.log(findDifference('bbcc', 'bbbcc')) //--> b

实际上第一部分可以省略（第一个for循环），我的解决方案可以解决整个问题，因为如果值不存在，则会是未定义的，而count !== undefined将返回该字母...

- emre-ozgun

Answer 7

我们最近需要一个快速的测试函数来从字符串中提取出一个单独的编辑，我在这里发布以帮助其他人。

这不是一个完整的差异算法，它只是从字符串的开头和结尾开始遍历，直到找到不匹配的字符，并返回结果。

/** Calculates the maximum spanning diff of two strings, or `null` if identical
 * @param {string} a 
 * @param {string} b */
function diff(a, b) {
    if ((a.length === b.length) && (a == b)) { return null; } // Identical
    
    let index = 0, endA = a.length, endB = b.length;
    const minLen = Math.min(endA, endB);
    
    while ((a[index] === b[index]) && (++index < minLen)); // Scan start
    while ((endA > index) && (endB > index) && (a[--endA] === b[--endB])); // Scan end
    return { index, before: a.substring(index, endA), after: b.substring(index, endB) };
}

console.log("Example:", diff("lebronjames", "lebronnjames"));
console.log("Same:", diff("This is a test", "This is a test"));
console.log("Mid:", diff("This is a test", "This is not a test"));
console.log("Start (A):", diff("**This is a test", "This is a test"));
console.log("Start (B):", diff("This is a test", "**This is a test"));
console.log("End (A):", diff("This is a test!!", "This is a test"));
console.log("End (B):", diff("This is a test", "This is a test!!"));

- Mike D Sutton

Answer 8

我获取两个字符串之间差异的方法。希望这个函数能帮助到某些人：

function getDifferences(a, b){
  
  let result = {
    state : true,
    diffs : []
  }

  if(a===b) return result;
  
  result.state = false;

  for (let index = 0; index < Math.max(a.length,b.length); index++) {
    if (a[index] !== b[index]) {
        result.diffs.push({index: index, old: a[index], new: b[index]})
    }
  }
  
  return result;
}

- Antonio Jurado

---

这难道不仅会比较两个完全相同长度的字符串吗？如果 b 比 a 更长，那么在 a 结束后的所有差异都不会被推入到 result.diffs 数组中吗？ - Brandon Tom

@BrandonTom 你说得对。我的主要想法是逐个查找字符串中的差异，忽略剩余部分，但是你的反思很有道理，这个函数可能会误导人。我会修改代码以查找所有内容。 - Antonio Jurado