C++のワードスクエア

単語のセットがあり（すべてが一意である）、すべてのワードスクエアを検索する必要があり、それらから構築できます。ここで、k番目の行と列がまったく同じ文字列を読み取る場合、単語のシーケンスは有効なワードスクエアを形成します。ここで、0≤k

したがって、入力が["area"、 "lead"、 "wall"、 "lady"、 "ball"]の場合、出力は[["wall"、 "area" 、"lead"、 "lady"]、["ball"、 "area"、 "lead"、 "lady"]]

これを解決するには、次の手順に従います-

• ノード構造を定義します。変数isEndと子ノードのリストがあります

• 1つの2D配列retを定義する

• 関数insertNode（）を定義します。これには、head、s、

  が必要です。

• ノード：=ヘッド

• 初期化i：=0の場合、i

  • x：=s [i]

  • ノードの子配列が空の場合、-

    • ノードのchild[x]：=新しいノード

  • node：=ノードのchild[x]

• isEnd of node：=true

• getAllWordsという関数を定義します。これには、idx、prefixmノード、および一時配列が必要です

• ノードが空の場合、-

  • 戻る

• ノードのisEndがtrueの場合、-

  • 温度の最後にcurrを挿入します

  • 戻る

• idx> =プレフィックスのサイズの場合、-

  • 各ノードについて、ノードの子になります-

    • getAllWords（idx、prefix、it.second、temp、curr + it.first）

• それ以外の場合-

  • x：=prefix [idx]

  • ノードの子が空でない場合、-

    • 戻る

  • getAllWords（idx + 1、プレフィックス、ノードの子[x]、temp、curr + x）

• 関数solve（）を定義します。これには、配列temp、idx、reqSize、head、

  が必要です。

• idxがreqSizeと同じ場合、-

  • retの最後にtempを挿入します

  • 戻る

• プレフィックス：=空の文字列

• 初期化i：=0の場合、i <温度のサイズの場合、更新（iを1増やします）、実行-

  • プレフィックス：=プレフィックス+ temp [i、idx]

• 可能な配列を定義する

• curr=頭

• getAllWords（0、prefix、curr、possible）

• 初期化i：=0の場合、i <可能なサイズの場合、更新（iを1増やします）、実行-

  • s：=可能[i]

  • tempの最後にsを挿入します

  • Solve（temp、idx + 1、reqSize、head）

  • tempから最後の要素を削除します

• メインの方法から、次のようにします-

• ヘッド=新しいノード

• 初期化i：=0の場合、i <単語のサイズの場合、更新（iを1増やします）、実行-

  • insertNode（head、words [i]）

• アレイの温度を定義する

• 初期化i：=0の場合、i <単語のサイズの場合、更新（iを1増やします）、実行-

  • s：=words [i]

  • tempの最後にsを挿入します

  • 解決（temp、1、単語のサイズ[0]、頭）

  • tempから最後の要素を削除します

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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, ],]