检测 2 个字符串中第一个差异的位置
Detect position of first difference in 2 strings
找到 Javascript 中任意两个字符串第一个差异位置的最简洁方法是什么?
var a = 'in the';
var b = 'in he';
findFirstDiffPos(a, b); // 3
var c = 'in the beginning';
findFirstDiffPos(a, c); // 6
您可以简单地遍历字符串并逐个字符地检查它。
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
的前缀,但长度不同。第 4 个 (基于 0) 字符在字符串 abcd
中不存在。您可以根据您的要求更改此逻辑
-1
: 字符串相等
更新: 正如@torazaburo 在评论中提到的,代码可以更简单 - 只需循环直到它们的长度 Math.max()
。它将起作用,因为 s[i]
for i >= s.length
将 return 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;
}
该函数可以使用一些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;
}
这将在最短字符串的末尾自动 return。
编辑
一些代码 golf 导致以下内容:
// 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;
}
但可读性可能会受到影响。选择的标准是什么?
for 循环版本的 torazaburo 的 while 循环(使用基本方法是值得的,因为它们通常比迭代器快得多,而且代码也不多,如果有的话):
function findFirstDiffPos(a, b) {
if (a === b) return -1;
for (var i=0; a[i] == b[i]; i++) {}
return i;
}
循环播放
循环方法可以更简洁地写成
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)上进行 polyfill。
这个替代方案比直接循环慢了惊人的 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);
}
正则表达式
同样在 "just for fun" 类别中,正则表达式解决方案。我们将从一个字符串构造一个 /^(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;
}
即使我们预编译正则表达式,这仍然比普通的旧循环慢五倍。
为了好玩,这里有一个衬垫。虽然它不是特别可读
const findFirstDiffPos = (a, b) => [a, b].sort((a, b) => b.length - a.length).reduce((a, b) => [...a].findIndex((c, i) => c !== b[i]))
找到 Javascript 中任意两个字符串第一个差异位置的最简洁方法是什么?
var a = 'in the';
var b = 'in he';
findFirstDiffPos(a, b); // 3
var c = 'in the beginning';
findFirstDiffPos(a, c); // 6
您可以简单地遍历字符串并逐个字符地检查它。
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
的前缀,但长度不同。第 4 个 (基于 0) 字符在字符串 abcd
中不存在。您可以根据您的要求更改此逻辑
-1
: 字符串相等
更新: 正如@torazaburo 在评论中提到的,代码可以更简单 - 只需循环直到它们的长度 Math.max()
。它将起作用,因为 s[i]
for i >= s.length
将 return 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;
}
该函数可以使用一些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;
}
这将在最短字符串的末尾自动 return。
编辑
一些代码 golf 导致以下内容:
// 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;
}
但可读性可能会受到影响。选择的标准是什么?
for 循环版本的 torazaburo 的 while 循环(使用基本方法是值得的,因为它们通常比迭代器快得多,而且代码也不多,如果有的话):
function findFirstDiffPos(a, b) {
if (a === b) return -1;
for (var i=0; a[i] == b[i]; i++) {}
return i;
}
循环播放
循环方法可以更简洁地写成
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)上进行 polyfill。
这个替代方案比直接循环慢了惊人的 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);
}
正则表达式
同样在 "just for fun" 类别中,正则表达式解决方案。我们将从一个字符串构造一个 /^(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;
}
即使我们预编译正则表达式,这仍然比普通的旧循环慢五倍。
为了好玩,这里有一个衬垫。虽然它不是特别可读
const findFirstDiffPos = (a, b) => [a, b].sort((a, b) => b.length - a.length).reduce((a, b) => [...a].findIndex((c, i) => c !== b[i]))