检测2个字符串中第一个差异的位置

Question

找到Javascript中任何两个字符串中的第一个差异的位置的最干净的方法是什么？

var a = 'in the';
var b = 'in he';
findFirstDiffPos(a, b); // 3

var c = 'in the beginning';
findFirstDiffPos(a, c); // 6 

Answer 1

您可以简单地遍历字符串并逐字符检查。

document.body.innerHTML += findFirstDiffPos("in he", "in the") + "<br/>";
document.body.innerHTML += findFirstDiffPos("abcd", "abcde") + "<br/>";
document.body.innerHTML += findFirstDiffPos("zxc", "zxc");

function findFirstDiffPos(a, b)
{
   var shorterLength = Math.min(a.length, b.length);

   for (var i = 0; i < shorterLength; i++)
   {
       if (a[i] !== b[i]) return i;
   }

   if (a.length !== b.length) return shorterLength;

   return -1;
}

输出为3 4 -1：3：因为字符串在位置3处不同4：字符串abcd是abcde的前缀，但是它们的长度不同。字符串abcd中不存在第4个（从0开始）字符。您可以根据需要更改此逻辑[-1：字符串相等

更新：正如@torazaburo在评论中提到的那样，代码甚至可以更容易-只需循环直到其长度的Math.max()。之所以会起作用，是因为s[i]的i >= s.length将返回undefined，并且条件将导致true。

document.body.innerHTML += findFirstDiffPos("in he", "in the") + "<br/>";
document.body.innerHTML += findFirstDiffPos("abcd", "abcde") + "<br/>";
document.body.innerHTML += findFirstDiffPos("zxc", "zxc");

function findFirstDiffPos(a, b)
{
  var longerLength = Math.max(a.length, b.length);
  for (var i = 0; i < longerLength; i++)
  {
     if (a[i] !== b[i]) return i;
  }

  return -1;
}

Answer 2

循环

循环方法可以写得更简洁一些

function findFirstDiffPos(a, b) {
  var i = 0;
  if (a === b) return -1;
  while (a[i] === b[i]) i++;
  return i;
}

根据jsperf，这种选择比这里的其他方法快5-20倍，这不足为奇。

Array#findIndex

由于我们正在尝试查找满足特定条件的索引，因此这似乎是findIndex的完美应用：

function findFirstDiffPos(a, b) {
  if (a.length < b.length) [a, b] = [b, a];
  return [...a].findIndex((chr, i) => chr !== b[i]);
}

（（我们需要更长的数组作为我们要查找的数组，因此如有必要，我们可以颠倒顺序。我们使用[...a]将字符串转换为字符数组。）

免责声明：这是一个ES6界面，您必须在IE（而不是Edge）上进行填充。

此替代方法比直线循环慢20倍。

递归

只是为了好玩，这是一个递归解决方案：

function findFirstDiffPos(a, b) {
  return function _iterate([headA, ...tailA], [headB, ...tailB], n) {
    return headA !== headB ? n : headA === undefined) ? -1 : _iterate(tailA, tailB, n+1);
  }(a.split(''), b.split(''), 0);
}

Regexp

也在“只是为了好玩”类别中，是一个正则表达式解决方案。我们将从一个字符串构造一个形式为/^(a(b(c)?)?)?/的正则表达式，并将其与另一个字符串进行匹配，然后检查匹配的长度。

function make_regexp(str) {
  var result = '';
  for (var i = str.length-1; i >= 0; i--)
    result = '(' + str[i] + result + ')?';
  return '^' + result;
}

function findFirstDiffPos(a, b) {
  return a === b ? -1 : b.match(make_regexp(a))[0].length;
}

即使我们预编译了正则表达式，它仍然比普通的旧循环慢五倍。

Answer 3

该功能可以使用某些ES5功能：

function firstDiff(a, b) {
  var idx;

  // Short ciruit if strings are the same
  if (a == b) return -1;

  // Go until difference found
  a.split('').every(function (c, i) {
    idx = i;
    return c == b[i]; 
  });
  return idx;
}

这将在最短字符串的末尾自动返回。

编辑

一些高尔夫代码会导致以下结果：

// Concise for loop
function firstDiff(a, b) {
  for (var i=0; i<a.length; i++)
    if (a[i] != b[i]) return i;
  return i<b.length? i : -1;
}

或使用ECMAScript 2015 findIndex：

function firstDiff(a, b) {
  var i = a.split('').findIndex(function(c, i) {return c != b[i]});
  return a == b? -1 : i == -1? a.length : i;
}

但是也许可读性受到影响。选择的标准是什么？

对于torazaburo的while循环工作的循环版本（值得使用基本方法，因为它们通常比迭代器快得多，并且如果有的话，也没有太多代码）：

function findFirstDiffPos(a, b) {
  if (a === b) return -1;
  for (var i=0; a[i] == b[i]; i++) {}
  return i;
}

Answer 4

为了好玩，这是一个班轮。虽然不是特别可读]

const findFirstDiffPos = (a, b) => [a, b].sort((a, b) => b.length - a.length).reduce((a, b) => [...a].findIndex((c, i) => c !== b[i]))