数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告