Giả sử chúng ta có một tập hợp các từ (tất cả đều là duy nhất), chúng ta phải tìm tất cả các ô vuông từ và chúng ta có thể xây dựng từ chúng. Ở đây, một chuỗi các từ tạo thành một hình vuông từ hợp lệ nếu hàng và cột thứ k đọc cùng một chuỗi chính xác, trong đó 0 ≤ k Vì vậy, nếu đầu vào là ["area", "lead", "wall", "lady", "ball"], thì đầu ra sẽ là [["wall", "area" , "lead", "lady"], ["ball", "area", "lead", "lady"]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Xác định cấu trúc nút, sẽ có một biến isEnd và danh sách các nút con
Xác định một mảng 2D ret
Xác định một hàm insertNode (), điều này sẽ lấy head, s,
nút:=head
để khởi tạo i:=0, khi i
x:=s [i]
nếu mảng con của nút trống, thì -
con [x] của nút:=nút mới
nút:=con [x] của nút
isEnd của nút:=true
Xác định một hàm có tên getAllWords, hàm này sẽ lấy idx, nút tiền tố và mảng tạm thời
nếu nút trống, thì -
trở lại
nếu isEnd của nút là true, thì -
chèn cuộn tóc vào cuối nhiệt độ
trở lại
if idx> =size of prefix, then -
cho mỗi nút nó trong con của nút -
getAll AdWords (idx, prefix, it.second, temp, curr + it.first)
Nếu không -
x:=tiền tố [idx]
nếu nút con không trống, thì -
trở lại
getAll AdWords (idx + 1, prefix, child [x] of node, temp, curr + x)
Xác định một hàm giải quyết (), điều này sẽ lấy một mảng temp, idx, reqSize, head,
nếu idx giống với reqSize, thì -
chèn tạm thời vào cuối ret
trở lại
tiền tố:=chuỗi trống
để khởi tạo i:=0, khi tôi
tiền tố:=prefix + temp [i, idx]
Xác định một mảng có thể có
curr =đầu
getAllWords (0, tiền tố, curr, có thể)
để khởi tạo i:=0, khi tôi
s:=có thể [i]
chèn s vào cuối tạm thời
giải quyết (temp, idx + 1, reqSize, head)
xóa phần tử cuối cùng khỏi tạm thời
Từ phương thức chính, hãy làm như sau -
head =nút mới
để khởi tạo i:=0, khi tôi
insertNode (head, words [i])
Xác định tạm thời mảng
để khởi tạo i:=0, khi tôi
s:=words [i]
chèn s vào cuối tạm thời
giải quyết (tạm thời, 1, kích thước của từ [0], head)
xóa phần tử cuối cùng khỏi tạm thời
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
b a l l a r e a l e a d l a d y
Ví dụ
#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));
} Đầu vào
{"area", "lead", "wall", "lady", "ball"} Đầu ra
[[wall, area, lead, lady, ],[ball, area, lead, lady, ],]
