【JavaScript】2つの文字列を比較して追加された1文字を見つける方法

プログラミングでは、2つの文字列 s と t が与えられる問題によく出会います。ここで文字列 t は、文字列 s をランダムにシャッフルした後、ランダムな位置にさらに1文字を追加して生成されたものです。

この記事では、両方の文字列を受け取り、t に追加されたその1文字を返すJavaScript関数の実装方法を解説します。

問題の例

たとえば、入力される文字列が次の場合を考えてみましょう。

const s = "abcd", t = "abcde";

このとき、期待される出力は次のとおりです。

const output = "e";

これは、追加された文字が「e」であるためです。

解決策：XOR（排他的論理和）を使う方法

「同じ値同士でXOR演算を行うと0になる」という性質を利用すると、効率的に差分の文字を特定できます。以下が実際のコード例です。

const s = "abcd", t = "abcde";
const findTheDifference = (s, t) => {
    let a = 0, b = 0; let charCode, i = 0;
    while(s[i]){
        a ^= s.charCodeAt(i).toString(2);
        b ^= t.charCodeAt(i).toString(2);
        i++;
    };
    b^=t.charCodeAt(i).toString(2);
    charCode = parseInt(a^b,2);
    return String.fromCharCode(charCode);
};
console.log(findTheDifference(s, t));

コードの解説

• charCodeAt() メソッドで各文字の文字コードを取得し、toString(2) で2進数の文字列に変換します。
• s の各文字コードは変数 a に、t の各文字コードは変数 b にXOR演算で蓄積していきます。
• ループ終了後、t の末尾にある余分な1文字も b に対してXOR演算で加えます。
• 最後に a ^ b の結果を10進数に戻し、String.fromCharCode() で文字に変換して返します。

実行結果

コンソールには次のように出力されます。

e

別のアプローチ：文字コードの合計値の差で求める方法

XOR以外にも、各文字コードの合計値の差を利用する、より直感的な方法があります。

const findTheDifference = (s, t) => {
    let sum = 0;
    for (let i = 0; i < t.length; i++) {
        sum += t.charCodeAt(i);
    }
    for (let i = 0; i < s.length; i++) {
        sum -= s.charCodeAt(i);
    }
    return String.fromCharCode(sum);
};
console.log(findTheDifference("abcd", "abcde")); // "e"

t の全文字コードの合計から s の全文字コードの合計を引けば、その差が追加された1文字のコードになります。いずれの方法も計算量は O(n) であり、文字列の長さに比例した効率で処理できる点が魅力です。