C++ 中的连接词
c++server side programmingprogramming更新于 2024/9/27 3:57:00
假设我们有一个单词列表。这些单词是不同的。我们必须设计一种算法来找出给定单词列表中的所有连接词。连接词实际上是一个字符串，它完全由给定数组中的至少两个较短的单词组成。
因此，如果单词类似于 ["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 的 child[x]，则 −
- 退出循环
- 否则
- curr := child[x] of curr
- 如果 isEnd of curr 为真，则 −
- ok := ok OR isPresent(str, head, i + 1, dp)
- return dp[idx] := ok
- 定义一个函数 insertNode()，它将获取 head, s，
- 创建一个节点 curr = head
- 初始化 i := 0，当 i < s 的大小，更新(将 i 增加 1)，执行 −
- x := s[i]
- 如果不是 curr 的 child[x]，则 −
- curr 的 child[x] := 创建一个新节点
- curr := child[x] of curr
- curr 的 isEnd := true
- 从 main 方法中，执行以下操作 −
- head := 创建一个新节点
- 根据单词长度对数组 words 进行排序
- 定义一个数组 ret
- 用于初始化 i := 0，当 i <单词的大小，更新(将 i 增加 1)，执行 −
- curr := words[i]
- 如果 curr 与 "" 相同，则 −
- 忽略以下部分，跳到下一次迭代
- 定义一个与 curr 大小相同的数组 dp，用 -1 填充
- 如果调用函数 isPresent(curr, head, 0, dp) 非零，则 −
- 在 ret 末尾插入 curr
- 否则
- 调用函数 insertNode(head, curr)
- return 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, ]
