假设我们有一组单词（所有单词都是唯一的），我们必须找到所有单词正方形，然后才能从中建立。如果第k行和第k列读取完全相同的字符串，则这里的单词序列构成有效的单词平方，其中0≤k <numRows和numColumns的最大值。因此，举例来说，单词序列[“ ball”，“ area”，“ lead”，“ lady”]将构成一个单词正方形，因为每个单词在水平和垂直方向上都读取相同的单词。
| b | 一种 | 升 | 升 |
| 一种 | [R | Ë | 一种 |
| 升 | Ë | 一种 | d |
| 升 | 一种 | d | ÿ |
因此，如果输入类似于[[区域]，“铅”，“墙”，“女士”，“球”]，则输出将为[[墙壁]，“区域”，“铅”，“女士” “]，[”球“，”区域“，”线索“，”女士“]]
为了解决这个问题，我们将遵循以下步骤-
定义一个节点结构，将有一个变量isEnd和一个子节点列表
定义一个2D阵列ret
定义一个函数insertNode()，它将以head，s，
节点：=头
对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-
节点的子节点[x]：=新节点
x：= s [i]
如果节点的子数组为空，则-
节点：=节点的子级[x]
节点的isEnd：= true
定义一个名为getAllWords的函数，它将使用idx，prefixm节点和temp数组
如果节点为空，则-
返回
如果节点的isEnd为true，则-
在临时结束时插入curr
返回
如果idx> =前缀的大小，则-
getAllWords（idx，前缀，it.second，temp，curr + it.first）
对于每个节点，它在节点的子节点中-
否则-
返回
x：=前缀[idx]
如果节点的子节点不为空，则-
getAllWords（idx + 1，前缀，节点的孩子[x]，临时，curr + x）
定义一个函数solve()，它将使用数组temp，idx，reqSize，head，
如果idx与reqSize相同，则-
在ret的末尾插入temp
返回
前缀：=空字符串
对于初始化i：= 0，当i <temp的大小时，更新（将i增加1），执行-
前缀：=前缀+ temp [i，idx]
定义一个可能的数组
curr =头
getAllWords（0，前缀，当前，可能）
对于初始化i：= 0，当i <可能的大小时，进行更新（将i增加1），执行-
s：=可能[i]
在temp的末尾插入s
解决（温度，idx + 1，reqSize，头）
删除temp中的最后一个元素
从主要方法中执行以下操作-
头=新节点
对于初始化i：= 0，当i <字长时，更新（将i增加1），执行-
insertNode（head，words [i]）
定义阵列温度
对于初始化i：= 0，当i <字长时，更新（将i增加1），执行-
s：=单词[i]
在temp的末尾插入s
solve（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, ],]