JavaScriptで解く「最長の文字列チェーン」：動的計画法による実装と解説

文字列チェーン（Word Chain）とは

ある単語 word1 の任意の位置にちょうど1文字を追加することで word2 と一致させられるとき、word1 は word2 の「先行語（predecessor）」であると定義します。たとえば、「abc」に「a」を挿入すると「abac」になるため、「abc」は「abac」の先行語です。

文字列チェーンとは、[word_1, word_2, ..., word_k]（k >= 1）という単語の列で、word_1 が word_2 の先行語、word_2 が word_3 の先行語、という関係が順番に成り立つものを指します。

問題の概要

文字列の配列 arr を唯一の引数として受け取る JavaScript 関数を作成します。配列内の各文字列はすべて英小文字で構成されています。この関数は、与えられた配列から選んだ単語で構成できる文字列チェーンのうち、最も長いものの長さを返す必要があります。

たとえば、次のような入力が与えられたとします。

const arr = ["a","b","ba","bca","bda","bdca"];

この場合の出力は次のようになります。

const output = 4;

出力の解説

最長の文字列チェーンの一例は「a」→「ba」→「bda」→「bdca」です。各ステップで1文字ずつ追加されているため、このチェーンの長さは4になります。

実装例

この問題を解くコードは次のとおりです。

const arr = ["a","b","ba","bca","bda","bdca"];
const longestStrChain = (arr) => {
    arr.sort((a, b) => a.length - b.length);
    const isPredecessor = (word1 = '', word2 = '') => {
        if(Math.abs(word1.length - word2.length) !== 1){
            return false;
        };
        for(let i = 0; i < word2.length; i++){
            const word = word2.slice(0, i) + word2.slice(i + 1);
            if(word === word1){
                return true;
            };
        };
        return false;
    };
    const array = [];
    let max = 0;
    for(let i = arr.length - 1; i >= 0; i--){
        array[i] = 1;
        for(let j = arr.length - 1; j > i; j--){
            if(isPredecessor(arr[i], arr[j])){
                array[i] = Math.max(
                    array[i],
                    1 + array[j],
                );
            };
        };
        max = Math.max(max, array[i]);
    };
    return max;
};
console.log(longestStrChain(arr));

出力結果

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

4

アルゴリズムのポイント

このコードは動的計画法（DP）を活用しています。まず配列を文字列の長さで昇順にソートし、短い単語から順に処理することで、先行語となり得る候補が必ず先に計算済みになるようにしています。

isPredecessor 関数は、まず2つの単語の長さの差がちょうど1であることを確認し、その上で長い方の単語から1文字を取り除いた文字列が短い方と一致するかどうかを判定します。

その後、各単語について「自分自身だけで構成されるチェーン（長さ1）」を初期値として設定し、より長い単語 j が自分の先行語になれる場合は array[j] + 1 との最大値を採用します。最終的に記録した最大値が答えとなります。計算量は O(n² × L)（n は単語数、L は単語の最大長）程度であり、効率的な解法といえます。