查找兩個字符串之間的額外字符

Question

如何以最佳方式在兩個字符串之間找到額外字符。

Ex1: S1 - 'abcd', S2 - 'abcxd', output - 'x' 
Ex2: S1 - '100001', S2 - '1000011', output - '1' 

我們可以通過線性遍歷每個字符爲O（n）比較做到這一點。我想要以更理想的方式做到這一點，比如在O(logn)

Answer 1

基準線方法（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