C++で解く最長文字列チェーン問題|動的計画法による実装例

問題概要

小文字だけで構成された単語のリストが与えられます。ある単語 word1 が別の単語 word2 の「先行詞(predecessor)」であるとは、word1 の任意の位置にちょうど1文字を追加するだけで word2 と一致させられる場合を指します。たとえば、「abc」は「abac」の先行詞です。

「単語チェーン」とは、[word_1, word_2, ..., word_k](k ≥ 1)という単語の列で、word_1 が word_2 の先行詞、word_2 が word_3 の先行詞、というように隣接する単語同士がすべて先行詞の関係になっているものを指します。ここでの目的は、与えられた単語リストから単語を選び、構成できる最も長い単語チェーンの長さを求めることです。

たとえば入力が ["a","b","ba","bca","bda","bdca"] の場合、出力は 4 になります。["a", "ba", "bda", "bdca"] が最長チェーンの一例となるためです。

解き方のポイント

この問題は動的計画法(DP)で効率よく解けます。鍵となるのは、「ある単語から1文字を取り除いた文字列」がその単語の候補となる先行詞であるという性質です。単語を短い順に処理していけば、各単語について「その単語で終わる最長チェーンの長さ」を確定できます。

アルゴリズムの手順

• マップ dp を定義します(n は単語配列のサイズ)。

• 単語配列を文字数の昇順でソートします。

• ret = 0 で初期化します。

• i を 0 から n − 1 までループさせます。

  • best = 0 で初期化します。

  • j を 0 から words[i] の長さ − 1 までループさせます。

    • word := words[i] の先頭から j−1 文字目までの部分文字列と、j+1 文字目以降の部分文字列を連結した文字列(= j 番目の1文字を削除した文字列)

    • best := best と dp[word] + 1 の大きい方

  • dp[words[i]] = best とします。

  • ret := ret と dp[words[i]] の大きい方

• ret を返します。

C++での実装例

以下が実際のコードです。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    static bool cmp(string s1, string s2){
        return s1.size() < s2.size();
    }
    int longestStrChain(vector<string>& words) {
        unordered_map <string, int> dp;
        int n = words.size();
        sort(words.begin(), words.end(), cmp);
        int ret = 0;
        for(int i = 0; i < n; i++){
            int best = 0;
            for(int j = 0; j < words[i].size(); j++){
                string word = words[i].substr(0, j) +
                words[i].substr(j + 1);
                best = max(best, dp[word] + 1);
            }
            dp[words[i]] = best;
            ret = max(ret, dp[words[i]]);
        }
        return ret;
    }
};
int main(){
    vector<string> v = {"a","b","ba","bca","bda","bdca"};
    Solution ob;
    cout << (ob.longestStrChain(v));
}

入力

["a","b","ba","bca","bda","bdca"]

出力

4

計算量について

ソートには O(n log n) のコストがかかります。その後、各単語について文字数 L 通りの「1文字削除パターン」を生成して DP テーブルを更新するため、全体の時間計算量は O(n × L²)(L は単語の最大長)となります。ハッシュマップ(unordered_map)を使うことで、部分文字列の参照は平均 O(1) で行えるため、非常に効率的な解法です。