JavaScriptで文字列が加法数（Additive Number）かどうかを判定する方法

加法数（Additive Number）とは

加法数とは、数字列を分割したときに、その各数が「加法シーケンス」を形成できるような数値文字列のことを指します。

有効な加法シーケンスには、少なくとも3つの数が含まれている必要があります。最初の2つの数を除き、シーケンス内の後続の各数は、直前の2つの数の和と等しくなければなりません。ここでは、「0」〜「9」の数字のみで構成された文字列が与えられたとき、それが加法数であるかどうかを判定する関数をJavaScriptで実装します。

注意： 加法シーケンス内の各数には、先頭にゼロを含めることはできません。そのため、1, 2, 03 や 1, 02, 3 のようなシーケンスは無効とみなされます。

例

たとえば、文字列「199100199」は加法数です。これは、次のような加法シーケンスに分解できるためです。

1, 99, 100, 199

1 + 99 = 100, 99 + 100 = 199

JavaScriptでの実装例

この判定を行うコードは以下のとおりです。

const str = "199100199";
const isAdditiveNumber = (numStr) => {
    // 3桁未満の文字列は加法シーケンスを形成できない
    if(numStr.length < 3) return false;
    let str = "";
    let seen = true;
    // 文字列の末尾から順に、シーケンスの最後の数を組み立てる
    for(let i = numStr.length - 1; i > 1; i--){
        str = `${numStr[i]}${str}`;
        // 末尾が0で終わる数は先頭ゼロの可能性があるためスキップ
        if(numStr[i] === "0") continue;
        let s = str;
        let s2 = numStr[i - 1]
        for(let j = i - 2; j >= 0; j--){
            // 複数桁かつ先頭がゼロの数は無効
            if(`${s2}`.startsWith("0") && s2.length > 1){
                s2 = `${numStr[j]}${s2}` seen = false;
            } else if(parseInt(s) >= parseInt(s2)){
                // 直前の2数の差分を求める
                let diff = s - s2;
                // 差分がそれより前の文字列の末尾に一致するか検証
                if(numStr.slice(0, j + 1).endsWith(diff)){
                    s = s2;
                    s2 = diff;
                    let ind = Math.floor(Math.log10(diff));
                    ind = ind < 0 ? 0 : ind
                    j -= ind;
                    seen = true;
                }else {
                    s2 = `${numStr[j]}${s2}`
                    seen = false;
                }
            }else{
                seen = false;
                break;
            }
        }
        if(seen) return seen;
    };
    return seen;
};
console.log(isAdditiveNumber(str));

このアルゴリズムのポイントは以下のとおりです。

• 文字列の末尾から順に、シーケンスの最後の数を1桁ずつ組み立てていきます。
• 複数桁の数で先頭がゼロになっている場合は無効な数として扱い、スキップします。
• 直前の2つの数の差分が、それより前の文字列の末尾に一致するかどうかを確認することで、シーケンスを逆方向へ検証していきます。

出力結果

上記のコードをコンソールで実行すると、次のように出力されます。

true

これは、文字列「199100199」が加法シーケンス 1, 99, 100, 199 を形成する有効な加法数であることを示しています。