C++で2つの辞書単語の連結による単語形成を判定する方法

問題概要

この問題では、辞書(単語の集合)と1つの文字列が与えられます。与えられた文字列が、辞書内の2つの単語を連結することで作れるかどうかを判定するのがタスクです。なお、同じ単語を繰り返して使用することは許されません。

具体例を見ながら理解していきましょう。

入力例

dictionary = {"hello", "tutorials", "program", "problem", "coding", "point"}
word = "tutorialspoint"

出力例

yes

説明

「tutorialspoint」は、「tutorials」と「point」という2つの辞書単語を連結することで作成できます。

解法アプローチ:トライ(Trie)を活用する

この問題を効率的に解くには、プレフィックス木(トライ)と呼ばれるデータ構造に、辞書内のすべての単語を事前に格納しておきます。その後、対象の単語の接頭辞(プレフィックス)をトライ内で検索し、辞書単語として一致する位置で文字列を2つに分割します。さらに残りの部分もトライ内に存在するかを調べ、両方が見つかれば true を、そうでなければ false を返します。

アルゴリズムの手順

1. 辞書内のすべての単語をトライに挿入する。
2. 対象の単語について、トライ内で一致する接頭辞(辞書に登録済みの単語)を先頭から検索する。
3. 一致する接頭辞が存在しない場合は false を返す。
4. 一致した位置で単語を分割し、残りの部分文字列がトライ内に存在するかを検索する。
5. 「分割位置 + 残り部分の長さ」が元の単語の長さと一致すれば true、それ以外は false を返す。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define SIZE (26)

struct TrieNode{
    TrieNode *children[26];
    bool isLeaf;
};

TrieNode *getNode(){
    TrieNode *newNode = new TrieNode;
    newNode->isLeaf = false;
    for (int i = 0; i < 26; i++)
        newNode->children[i] = NULL;
    return newNode;
}

// 辞書の単語をトライに挿入する
void insert(TrieNode *root, string Key){
    int n = Key.length();
    TrieNode *pCrawl = root;
    for (int i = 0; i < n; i++){
        int index = char_int(Key[i]);
        if (pCrawl->children[index] == NULL)
            pCrawl->children[index] = getNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isLeaf = true;
}

// キー文字列に対して、トライ内に存在する最長の接頭辞の長さを返す
int prefixSearch(struct TrieNode *root, string key){
    int pos = -1, level;
    struct TrieNode *pCrawl = root;
    for (level = 0; level < key.length(); level++){
        int index = char_int(key[level]);
        if (pCrawl->isLeaf == true)
            pos = level;
        if (!pCrawl->children[index])
            return pos;
        pCrawl = pCrawl->children[index];
    }
    if (pCrawl != NULL && pCrawl->isLeaf)
        return level;
    return pos;
}

// 単語が2つの辞書単語の連結で作れるかを判定する
bool isWordCreated(struct TrieNode* root, string word){
    int len = prefixSearch(root, word);
    if (len == -1)
        return false;
    string split_word(word, len, word.length() - len);
    int split_len = prefixSearch(root, split_word);
    return (len + split_len == word.length());
}

int main() {
    vector<string> dictionary = {"tutorials", "program", "solving", "point"};
    string word = "tutorialspoint";
    TrieNode *root = getNode();
    for (int i = 0; i < dictionary.size(); i++)
        insert(root, dictionary[i]);
    cout << "Word formation using dictionary is ";
    isWordCreated(root, word) ? cout << "possible" : cout << "not possible";
    return 0;
}

出力

Word formation using dictionary is possible

計算量の評価

• 時間計算量: トライの構築には O(N × L)(N は辞書内の単語数、L は単語の平均長)。単語の判定処理は O(M)(M は対象の単語の長さ)で完了します。
• 空間計算量: トライのノード数に依存し、最大で O(N × L) のメモリが必要です。

まとめ

トライを使うことで、辞書内の接頭辞検索を高速に行えるため、全組み合わせを総当たりで試すよりも効率的に「2単語の連結で作れるか」を判定できます。文字列検索や辞書系の問題では非常に応用範囲の広いテクニックなので、ぜひマスターしておきましょう。