資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的連線詞
假設我們有一系列單詞。這些單詞是不同的。我們必須設計一種演算法來查詢給定單詞列表中的所有連線詞。連線詞實際上是一個字串，它完全由給定陣列中的至少兩個較短的單片語成。
因此，如果單詞類似於 ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"]，則輸出將為 ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"]
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 isPresent()，它將接收 str、head、idx 和一個數組 dp，
- 如果 idx >= str 的大小，則：
- 返回 true
- 如果 dp[idx] 不等於 -1，則：
- 返回 dp[idx]
- 建立一個節點 curr := head
- ok := false
- 對於初始化 i := idx，當 i < str 的大小，更新（將 i 增加 1），執行：
- x := str[i]
- 如果 curr 的子節點中不存在 x，則：
- 退出迴圈
- 否則
- curr := curr 的子節點 x
- 如果 curr 的 isEnd 為 true，則：
- ok := ok OR isPresent(str, head, i + 1, dp)
- 返回 dp[idx] := ok
- 定義一個函式 insertNode()，它將接收 head 和 s，
- 建立一個節點 curr = head
- 對於初始化 i := 0，當 i < s 的大小，更新（將 i 增加 1），執行：
- x := s[i]
- 如果 curr 的子節點中不存在 x，則：
- curr 的子節點 x := 建立一個新節點
- curr := curr 的子節點 x
- curr 的 isEnd := true
- 從主方法中執行以下操作：
- head := 建立一個新節點
- 根據單詞長度對陣列 words 進行排序
- 定義一個數組 ret
- 對於初始化 i := 0，當 i < words 的大小，更新（將 i 增加 1），執行：
- curr := words[i]
- 如果 curr 與 "" 相同，則：
- 忽略以下部分，跳到下一個迭代
- 定義一個與 curr 大小相同的陣列 dp，用 -1 填充它
- 如果呼叫函式 isPresent(curr, head, 0, dp) 的返回值不為零，則：
- 將 curr 插入到 ret 的末尾
- 否則
- 呼叫函式 insertNode(head, curr)
- 返回 ret
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class Solution {
public:
bool isPresent(string str, Node* head, int idx, vector <int>& dp){
if(idx >= str.size())return true;
if(dp[idx] != -1)return dp[idx];
Node* curr = head;
bool ok = false;
for(int i = idx; i < str.size(); i++){
char x = str[i];
if(!curr->child[x]){
break;
}else{
curr = curr->child[x];
}
if(curr->isEnd){
ok |= isPresent(str, head, i + 1, dp);
}
}
return dp[idx] = ok;
}
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
void insertNode(Node* head, string s){
Node* curr = head;
for(int i = 0; i < s.size(); i++){
char x = s[i];
if(!curr->child[x]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
vector <string> ret;
for(int i = 0; i < words.size(); i++){
string curr = words[i];
if(curr=="")continue;
vector <int> dp(curr.size(), -1);
if(isPresent(curr, head, 0, dp)){
ret.push_back(curr);
}else{
insertNode(head, curr);
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"};
print_vector(ob.findAllConcatenatedWordsInADict(v));
}輸入
{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}輸出
[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]
更新於： 2020-06-01
142 次檢視
廣告