数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中的单词方阵
假设我们有一组单词（所有单词都是唯一的），我们需要找到所有可以从中构建的单词方阵。如果一个单词序列满足第k行和第k列读取的字符串完全相同，则该序列构成一个有效的单词方阵，其中0 ≤ k < 行数和列数的最大值。例如，单词序列["ball","area","lead","lady"] 将构成一个单词方阵，因为每个单词在水平和垂直方向上读取的结果都相同。
| b | a | l | l |
| a | r | e | a |
| l | e | a | d |
| l | a | d | y |
因此，如果输入类似于["area","lead","wall","lady","ball"]，则输出将为[[ "wall", "area", "lead", "lady"], ["ball", "area", "lead", "lady"]]
为了解决这个问题，我们将遵循以下步骤：
定义一个节点结构，其中包含一个isEnd变量和一个子节点列表。
定义一个二维数组ret。
定义一个函数insertNode()，它将接收head和s作为参数。
node := head
for 初始化 i := 0，当 i < s 的大小，更新（i增加1），执行：
x := s[i]
如果node的子数组为空，则：
node的child[x] := 新节点
node := node的child[x]
node的isEnd := true
定义一个名为getAllWords的函数，它将接收idx，prefix，node和temp数组作为参数。
如果node为空，则：
返回。
如果node的isEnd为true，则：
将curr插入到temp的末尾。
返回。
如果idx >= prefix的大小，则：
对于node的每个子节点it：
getAllWords(idx, prefix, it.second, temp, curr + it.first)
否则：
x := prefix[idx]
如果node的child不为空，则：
返回。
getAllWords(idx + 1, prefix, node的child[x], temp, curr + x)
定义一个函数solve()，它将接收一个数组temp，idx，reqSize和head作为参数。
如果idx等于reqSize，则：
将temp插入到ret的末尾。
返回。
prefix := 空字符串
for 初始化 i := 0，当 i < temp的大小，更新（i增加1），执行：
prefix := prefix + temp[i, idx]
定义一个数组possible。
curr = head
getAllWords(0, prefix, curr, possible)
for 初始化 i := 0，当 i < possible的大小，更新（i增加1），执行：
s := possible[i]
将s插入到temp的末尾。
solve(temp, idx + 1, reqSize, head)
从temp中删除最后一个元素。
在主方法中执行以下操作：
head = 新节点
for 初始化 i := 0，当 i < words的大小，更新（i增加1），执行：
insertNode(head, words[i])
定义一个数组temp。
for 初始化 i := 0，当 i < words的大小，更新（i增加1），执行：
s := words[i]
将s插入到temp的末尾。
solve(temp, 1, words[0]的大小, head)
从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, ],]
244 次浏览
