ワードブレイク問題とは？文字列を辞書の単語に分割するアルゴリズムとC++実装例

この問題では、スペースなしで連結された1つの文と、有効な英単語からなる辞書が与えられます。私たちの課題は、この文を辞書に含まれる単語の組み合わせに分割できるすべての方法を見つけることです。

解法の基本的な考え方は、文字列の左端から順に探索を行い、辞書に存在する有効な単語が見つかったら、その残りの部分に対して同じ処理を再帰的に適用するというものです。

入力と出力

入力:
有効な単語の集合（辞書）、および複数の単語がスペースなしで連結された文字列。
辞書: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
対象文字列: "ilovemangoicecream"

出力:
文字列を辞書内の単語に分割できるすべてのパターン。
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream

この例のように、1つの文字列に対して複数の分割パターンが存在する場合があります。そのため、すべての可能性を網羅的に調べる必要があるのです。

アルゴリズム

以下の関数 wordBreak(string, n, result) を用いて問題を解きます。

入力 − 対象の文字列、文字列の長さ、これまでに分割された結果の文字列。

出力 − 辞書を用いて文字列を分割した結果。

Begin
    for i := 0 to n, do
        subStr := 与えられた文字列の先頭から (0..i) までの部分文字列
        if subStr が辞書に存在するならば, then
            if i = n ならば, then
                result := result + subStr
                結果を表示する
                return
            wordBreak((i..n-i) の部分文字列, n-i, result + subStr + 空白)
    done
End

このアルゴリズムはバックトラッキング（探索と巻き戻し）の考え方に基づいています。前方の部分文字列が辞書に見つかれば、残りの文字列に対して再帰的に同じ処理を試みます。途中で失敗しても、別の候補に戻って探索を続けることで、すべての分割パターンを列挙できます。

C++による実装例

#include <iostream>
#define N 13
using namespace std;

string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and",
                        "go","i","love","ice","cream"};

int isInDict(string word){     // 単語が辞書に存在するかどうかをチェックする
    for (int i = 0; i < N; i++)
        if (dictionary[i].compare(word) == 0)
            return true;
    return false;
}

void wordBreak(string str, int n, string result) {
    for (int i=1; i<=n; i++) {
        string subStr = str.substr(0, i);      // 文字列の先頭から i 番目までの部分文字列を取得
        if (isInDict(subStr)) {       // subStr が辞書に見つかった場合
            if (i == n) {
                result += subStr; // 部分文字列を結果に追加
                cout << result << endl;
                return;
            }
            wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");     // それ以外の場合は残りの部分をさらに分割
        }
    }
}

int main() {
    string str="iloveicecreamandmango";
    wordBreak(str, str.size(),"");
}

実行結果

i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream

このように、「iloveicecreamandmango」という文字列に対して、4通りの分割パターンが出力されました。「man go」と「mango」、「ice cream」と「icecream」のように、異なる単語の組み合わせで同じ文字列を表現できることが確認できます。

なお、この実装では辞書検索を線形探索で行っているため、計算量は O(N) です。辞書サイズが大きい場合は、ハッシュセット（std::unordered_set）やトライ木を使用することで、検索を高速化できます。