단어 세트가 있다고 가정하고(모두 고유함) 모든 단어 사각형을 찾아야 하고 그로부터 구성할 수 있습니다. 여기서 k번째 행과 열이 정확히 동일한 문자열을 읽는 경우 일련의 단어는 유효한 단어 정사각형을 형성합니다. 여기서 0 ≤ k 따라서 입력이 ["area","lead","wall","lady","ball"]과 같으면 출력은 [[ "wall", "area" , "리드", "레이디"], ["볼", "영역", "리드", "레이디"]]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
노드 구조를 정의하면 isEnd 변수와 자식 노드 목록이 있습니다.
하나의 2D 배열 ret 정의
insertNode() 함수를 정의하면 head, s,
노드 :=헤드
initialize i :=0의 경우 i
x :=s[i]
노드의 자식 배열이 비어 있으면 -
노드의 자식[x]:=새 노드
노드 :=노드의 자식[x]
isEnd of node :=true
getAllWords라는 함수를 정의합니다. 이것은 idx, prefixm 노드 및 임시 배열을 사용합니다.
노드가 비어 있으면 -
반환
노드의 isEnd가 참이면 -
temp의 끝에 curr 삽입
반환
idx>=접두어 크기인 경우 -
노드의 자식에 있는 각 노드에 대해 -
getAllWords(idx, 접두사, it.second, temp, curr + it.first)
그렇지 않으면 -
x :=접두어[idx]
노드의 자식이 비어 있지 않으면 -
반환
getAllWords(idx + 1, prefix, 노드의 자식[x], temp, curr + x)
solve() 함수를 정의하면 배열 temp, idx, reqSize, head,
idx가 reqSize와 같으면 -
ret 끝에 temp 삽입
반환
접두사 :=빈 문자열
초기화 i :=0의 경우, i <임시 크기의 경우 업데이트(i를 1만큼 증가), -
접두사 :=접두사 + 임시[i, idx]
가능한 배열 정의
커 =머리
getAllWords(0, 접두사, 현재, 가능)
initialize i :=0의 경우, i <가능한 크기일 때 업데이트(i를 1만큼 증가), −
s :=가능[i]
temp의 끝에 s 삽입
해결(temp, idx + 1, reqSize, 헤드)
temp에서 마지막 요소 삭제
주요 방법에서 다음을 수행하십시오 -
헤드 =새 노드
for initialize i :=0, i <단어 크기일 때 업데이트(i 1 증가), −
insertNode(머리, 단어[i])
어레이 온도 정의
for initialize i :=0, i <단어 크기일 때 업데이트(i 1 증가), −
s :=단어[i]
temp의 끝에 s 삽입
해결(temp, 1, 단어 크기[0], head)
temp에서 마지막 요소 삭제
리턴 렛
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −b a l l a r e a l e a d l a d y
예시
#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, ],]
