C++で同義文をすべて生成する方法：Union-FindとDFSによる実装解説

問題概要

同義語ペアのリスト synonyms と1つの文 text が与えられます。文中の各単語を、つながりのあるすべての同義語で置き換えた結果として考えられる文をすべて求め、辞書順にソートして返すのが目的です。

たとえば、入力が次のとおりだったとします。

• synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]]
• text = "I am happy today but was sad yesterday"

この場合、「happy」は joy・cheerful とつながっており、「sad」は sorrow とつながっています。したがって、出力は次の6通りになります。

["I am cheerful today but was sad yesterday",
 "I am cheerful today but was sorrow yesterday",
 "I am happy today but was sad yesterday",
 "I am happy today but was sorrow yesterday",
 "I am joy today but was sad yesterday",
 "I am joy today but was sorrow yesterday"]

解法のポイント

この問題は、Union-Find（素集合データ構造）で同義語同士のつながりをグループ化し、深さ優先探索（DFS）で置き換えの全パターンを列挙するのが定石です。

全体の流れ

1. find(): ある単語が属するグループの代表元（根）を再帰的に求めます。
2. unionNode(): 2つの単語を同じグループに統合します。
3. getString(): 文を空白区切りで分割し、単語の配列に変換します。
4. dfs(): 各位置の単語について、同義語グループに属していればグループ内の全単語で置き換えを試しながら、再帰的に文を組み立てます。
5. generateSentences(): 上記をまとめて実行し、最後に結果をソートして返します。

アルゴリズムの詳細

まず、parent・color・groupByColor の3つのマップを用意します。

• parent: Union-Find の親ポインタを保持します。
• color: 各グループの代表元に一意の番号（色）を割り当てます。
• groupByColor: 同じ色（グループ）に属する単語の集合を set で管理します。

find(s) は、parent[s] が自分自身であれば s をそのまま返し、そうでなければ再帰的に根を辿ります（経路圧縮も行われます）。unionNode(a, b) は、それぞれの根 x と y を求め、異なる場合は parent[x] = y として統合します。

generateSentences() では、まずすべての同義語ペアに対して unionNode を呼び出してグループを作成します。続いて、各ペアの代表元に色番号を振り、color マップと groupByColor マップを更新していきます。

その後、getString(t) で文を単語配列に分解し、dfs(strings, 0) を呼び出します。dfs 内では、現在の単語がどのグループにも属さない場合はそのまま次の単語へ進み、属している場合は groupByColor から同義語の集合を取り出し、そのすべてについて再帰呼び出しを行います。すべての単語を処理し終えたら、完成した文を ans に追加します。

最後に ans をソートすれば、辞書順に並んだすべての同義文が得られます。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   map <string, string> parent;
   map <string, int> color;
   map <int, set<string> > groupByColor;
   string find(string s){
      if(parent[s] == s)return s;
         parent[s] = find(parent[s]);
      return parent[s];
   }
   void unionNode(string a, string b){
      string x = find(a);
      string y = find(b);
      if(x == y)return;
         parent[x] = y;
   }
   vector <string> ans;
   vector <string> getString(string t){
      vector <string> temp;
      int end = 0;
      string curr = "";
      for(;end < t.size(); end++){
         if(t[end] == ' '){
            temp.push_back(curr);
            curr = "";
            continue;
         }
         curr += t[end];
      }
      temp.push_back(curr);
      return temp;
   }
   void dfs(vector <string> &strings, int idx, string temp = ""){
      if(idx == strings.size()){
         ans.push_back(temp);
         return;
      }
      string current = strings[idx];
      if(color.find(current) == color.end()){
         dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" "));
      }
      else{
         set <string> x = groupByColor[color[current]];
         set <string> :: iterator z = x.begin();
         while(z != x.end()){
            dfs(strings, idx + 1, temp + *z + (idx+1 == strings.size()?"":" "));
            z++;
         }
      }
   }
   void seeGroups(){
      map <int, set <string> > :: iterator i = groupByColor.begin();
      while(i != groupByColor.end()){
         set <string> x = i->second;
         set <string> :: iterator z = x.begin();
         while(z != x.end()){
            z++;
         }
         cout << endl;
         i++;
      }
   }
   vector<string> generateSentences(vector<vector<string>>& s, string t) {
      int n = s.size();
      for(int i = 0; i < n; i++){
         string x = s[i][0];
         string y = s[i][1];
         if(parent.find(x) == parent.end())parent[x] = x;
            if(parent.find(y) == parent.end())parent[y] = y;
               unionNode(x,y);
      }
      int c = 1;
      for(int i = 0; i < n; i++){
         string x = s[i][0];
         string z = s[i][1];
         string y = find(x);
         if(color.find(y) == color.end()){
            color[y] = c;
            c++;
         }
         color[x] = color[y];
         color[z] = color[y];
         if(groupByColor.find(color[x]) == groupByColor.end()){
            set <string> ss;
            ss.insert(x);
            ss.insert(y);
            groupByColor[color[x]] = ss;
         }
         else{
            groupByColor[color[x]].insert(x);
            groupByColor[color[x]].insert(z);
         }
      }
      vector <string> strings = getString(t);
      dfs(strings, 0);
      sort(ans.begin(), ans.end());
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<string>> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}};
   print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday"));
}

入力例

[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"

出力例

[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday]

まとめ

同義語の連結関係を Union-Find で管理し、DFS で全パターンを列挙することで、与えられた文から作れるすべての同義文を効率的に生成できます。ただし、結果の件数は各グループの候補数の積に比例して増加するため、入力サイズが大きい場合は計算量に注意が必要です。