C++で文字配列から作成できるすべての有効な単語を出力する方法

問題の概要

この問題では、単語の集合と文字の配列が与えられ、その配列に含まれる文字だけを使って作成できる単語をすべて見つけ出します。

入力と出力の例

入力 : words[] : {'go' , 'hi' , 'run' , 'on' , 'hog' , 'gone'}
       Char[] : {'a' , 'o' , 'h' , 'g'}
出力 : go , hog

説明: 与えられた単語の中で、文字配列 {'a', 'o', 'h', 'g'} のみで構成できるのは「go」と「hog」の2つです。「hi」や「run」などは配列に存在しない文字を含むため、有効な単語として出力されません。

解決アプローチ:トライ(Trie)データ構造

この問題を効率的に解くには、トライ(Trie)と呼ばれるデータ構造を利用します。トライは文字列の集合を木構造で管理する仕組みで、まずすべての単語をトライに挿入し、その後、文字配列に含まれる文字をたどりながらトライを探索することで、作成可能な単語をすべて見つけられます。

アルゴリズムの流れ

1. 辞書内のすべての単語をトライに挿入します。
2. 文字配列の各文字について、サイズ26のブール型ハッシュ配列で使用可否のフラグを立てます。
3. ハッシュ配列で有効とマークされた文字に対応する子ノードがトライに存在する場合、そのノードへ再帰的に移動しながら単語を構築します。
4. 葉ノード(単語の終端)に到達した時点で、構築中の文字列を有効な単語として出力します。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define int_to_char(c) ((char)c + (char)'a')
struct TrieNode{
    TrieNode *Child[26];
    bool leaf;
};
TrieNode *getNode(){
    TrieNode * newNode = new TrieNode;
    newNode->leaf = false;
    for (int i =0 ; i< 26 ; i++)
        newNode->Child[i] = NULL;
    return newNode;
}
void insertnode(TrieNode *root, char *Key){
    int n = strlen(Key);
    TrieNode * pChild = root;
    for (int i=0; i<n; i++){
        int index = char_int(Key[i]);
        if (pChild->Child[index] == NULL)
            pChild->Child[index] = getNode();
        pChild = pChild->Child[index];
    }
    pChild->leaf = true;
}
void vaidword(TrieNode *root, bool Hash[], string str){
    if (root->leaf == true)
        cout << str << "\t" ;
    for (int K =0; K < 26; K++){
        if (Hash[K] == true && root->Child[K] != NULL ){
            char c = int_to_char(K);
            vaidword(root->Child[K], Hash, str + c);
        }
    }
}
void PrintAllWords(char Arr[], TrieNode *root, int n){
    bool Hash[26];
    for (int i = 0 ; i < n; i++)
        Hash[char_int(Arr[i])] = true;
    TrieNode *pChild = root ;
    string str = "";
    for (int i = 0 ; i < 26 ; i++){
        if (Hash[i] == true && pChild->Child[i] ){
            str = str+(char)int_to_char(i);
            vaidword(pChild->Child[i], Hash, str);
            str = "";
        }
    }
}
int main(){
    char Dict[][20] = {"go" , "hi" , "run" , "on" , "hog" , "gone"} ;
    TrieNode *root = getNode();
    int n = sizeof(Dict)/sizeof(Dict[0]);
    for (int i=0; i<n; i++)
        insertnode(root, Dict[i]);
    char arr[] = {'a', 'o', 'g', 'h'} ;
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"The words which are valid\t";
    PrintAllWords(arr, root, N);
    return 0;
}

出力結果

The words which are valid go hog

まとめ

トライデータ構造を活用することで、文字配列から生成可能なすべての単語を効率的に列挙できます。各文字の使用可否をハッシュ配列で管理し、トライを深さ優先で探索するこの手法は、単語数や文字数が多い場合でも高いパフォーマンスを発揮します。