資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
