C++で解くワードスクエア問題：トライ木とバックトラッキングによる実装方法

ワードスクエアとは？

ユニークな単語の集合が与えられたとき、そこから作成できるすべての「ワードスクエア（単語正方形）」を見つけることを考えましょう。単語のシーケンスが有効なワードスクエアとなる条件は、k番目の行とk番目の列がまったく同じ文字列を読み取ることです（ここで 0 ≤ k < 行数と列数の最大値）。

例えば、単語列 ["ball", "area", "lead", "lady"] はワードスクエアを構成します。どの単語も横方向にも縦方向にも同じように読めるからです。

したがって、入力が ["area", "lead", "wall", "lady", "ball"] の場合、出力は [["wall", "area", "lead", "lady"], ["ball", "area", "lead", "lady"]] となります。

解法のアプローチ

この問題を効率的に解くには、トライ木（接頭辞木）とバックトラッキングを組み合わせます。以下の手順で進めます。

1. ノード構造体の定義： 終端フラグ isEnd と子ノードのマップを持つ構造体を定義します。

2. 結果格納用の2次元配列 ret を定義します。

3. insertNode() 関数： ヘッドノードと文字列を受け取り、トライ木に単語を挿入します。各文字に対して子ノードが存在しなければ新規ノードを作成し、最後のノードの isEnd を true に設定します。

4. getAllWords() 関数： インデックス idx、接頭辞 prefix、現在のノード、結果配列 temp を受け取ります。

   • ノードが空なら処理を終了します。
   • ノードが終端（isEnd = true）なら、現在の文字列 curr を temp に追加して終了します。
   • idx が接頭辞の長さ以上の場合は、すべての子ノードを再帰的に探索します。
   • そうでなければ、接頭辞の idx 番目の文字に対応する子ノードへ進みます。該当する子が存在しない場合は打ち切ります。

5. solve() 関数： 単語配列 temp、インデックス idx、必要なサイズ reqSize、ヘッドノードを受け取ります。

   • idx が reqSize と等しければ、temp を ret に追加します。
   • それ以外の場合、すでに配置済みの単語から idx 番目の文字を集めて接頭辞 prefix を組み立てます。
   • getAllWords() を呼び出し、その接頭辞にマッチする候補単語の一覧 possible を取得します。
   • 各候補について temp に追加し、idx + 1 で再帰呼び出しを行った後、バックトラッキングとして末尾要素を削除します。

6. メイン処理：

   • ヘッドノードを作成し、すべての単語をトライ木に挿入します。
   • 各単語を最初の行として temp に入れ、solve(temp, 1, words[0] のサイズ, head) を呼び出します。
   • 最終的に ret を返します。

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
struct Node {
   bool isEnd;
   map<char, Node *> child;
};
class Solution {
public:
   vector<vector<string>> ret;
   void insertNode(Node *head, string &s) {
      Node *node = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!node->child[x]) {
            node->child[x] = new Node();
         }
         node = node->child[x];
      }
      node->isEnd = true;
   }
   void getAllWords(int idx, string prefix, Node *node, vector<string>&temp,
      string curr = "") {
         if (!node)
            return;
         if (node->isEnd) {
            temp.push_back(curr);
            return;
         }
         if (idx >= prefix.size()) {
            for (auto &it : node->child) {
               getAllWords(idx, prefix, it.second, temp, curr + it.first);
            }
         }
         else {
            char x = prefix[idx];
            if (!node->child[x])
               return;
            getAllWords(idx + 1, prefix, node->child[x], temp, curr + x);
         }
   }
   void solve(vector<string> &temp, int idx, int reqSize, Node *head){
      if (idx == reqSize) {
         ret.push_back(temp);
         return;
      }
      string prefix = "";
      for (int i = 0; i < temp.size(); i++) {
         prefix += temp[i][idx];
      }
      vector<string> possible;
      Node *curr = head;
      getAllWords(0, prefix, curr, possible);
      for (int i = 0; i < possible.size(); i++) {
         string s = possible[i];
         temp.push_back(s);
         solve(temp, idx + 1, reqSize, head);
         temp.pop_back();
      }
   }
   vector<vector<string>> wordSquares(vector<string> &words) {
      ret.clear();
      Node *head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      vector<string> temp;
      for (int i = 0; i < words.size(); i++) {
         string s = words[i];
         temp.push_back(s);
         solve(temp, 1, (int)words[0].size(), head);
         temp.pop_back();
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<string> v = {"area", "lead", "wall", "lady", "ball"};
   print_vector(ob.wordSquares(v));
}

入力

{"area", "lead", "wall", "lady", "ball"}

出力

[[wall, area, lead, lady],[ball, area, lead, lady]]

まとめ

このアルゴリズムでは、トライ木によって接頭辞に一致する候補単語の検索を高速化し、バックトラッキングで各行に適切な単語を順に配置していきます。全探索に比べて無駄な分岐を大幅に削減できるため、単語数や文字数が多いケースでも実用的な速度で動作します。ワードスクエアのような制約充足型のパズル問題では、この「データ構造＋探索」の組み合わせが非常に有効です。