如何以最佳方式在两个字符串之间找到额外字符。查找两个字符串之间的额外字符
Ex1: S1 - 'abcd', S2 - 'abcxd', output - 'x'
Ex2: S1 - '100001', S2 - '1000011', output - '1'
我们可以通过线性遍历每个字符为O(n)比较做到这一点。我想要以更理想的方式做到这一点,比如在O(logn)
如何以最佳方式在两个字符串之间找到额外字符。查找两个字符串之间的额外字符
Ex1: S1 - 'abcd', S2 - 'abcxd', output - 'x'
Ex2: S1 - '100001', S2 - '1000011', output - '1'
我们可以通过线性遍历每个字符为O(n)比较做到这一点。我想要以更理想的方式做到这一点,比如在O(logn)
基准线方法(O(n)):只比较每个周期两侧的字符和缩小范围。
function findDiffChar(base, baseExtraChar) {
let extraLastIndex = base.length;
let lastIndex = extraLastIndex - 1;
for (let i = 0; i < extraLastIndex/2; i++) {
console.log(`Loop: ${i}`);
if (base[i] !== baseExtraChar[i])
return baseExtraChar[i];
if (base[lastIndex - i] !== baseExtraChar[extraLastIndex - i])
return baseExtraChar[extraLastIndex - i];
}
return false;
}
console.log(findDiffChar('FOOOOOAR', 'FOOOOOBAR')); // B
使用二进制搜索(O(log n)的)改进的方法:比较两半,直到你已经将范围缩小到一个字符。
function findDiffChar(base, baseExtraChar) {
if (baseExtraChar.length === 1) return baseExtraChar.charAt(0);
let halfBaseLen = Number.parseInt(base.length/2) || 1;
let halfBase = base.substring(0,halfBaseLen);
let halfBaseExtra = baseExtraChar.substring(0,halfBaseLen);
return (halfBase !== halfBaseExtra)
? findDiffChar(halfBase, halfBaseExtra)
: findDiffChar(base.substring(halfBaseLen),baseExtraChar.substring(halfBaseLen));
}
console.log(findDiffChar('FOOOOAR', 'FOOOOBAR')); // B
console.log(findDiffChar('---------', '--------X')); // X
console.log(findDiffChar('-----------', '-----X-----')); // X
console.log(findDiffChar('------------', '---X--------')); // X
console.log(findDiffChar('----------', '-X--------')); // X
console.log(findDiffChar('----------', 'X---------')); // X
但这仍然是线性的。 O(n) – user3422229
@ user3422229更新了备用递归策略。 – Jecoms
你肯定只有1 XTRA性格吗? – 2016-12-16 19:13:52
是的。只有1个字符。需要找到那个额外的字符。 – user3422229
双方攻击,直到一方不同。或者,你可以让两个char数组产生一个新的数组,每个字符的差异结果(使用'charCodeAt()')。第一个非零是差异。 – Jecoms