数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的同义词句子
假设我们有一组成对的同义词和一个句子文本，我们需要找到所有可能的同义句，并按字典顺序排序。
例如，如果输入为 synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]]，text = "I am happy today but was sad yesterday"，则输出将为 ["I am cheerful today but was sad yesterday", "I am cheerful today but was sorrow yesterday", "I am happy today but was sad yesterday", "I am happy today but was sorrow yesterday", "I am joy today but was sad yesterday", "I am joy today but was sorrow yesterday"]
为了解决这个问题，我们将遵循以下步骤：
定义映射 parent、color 和 groupByColor
定义一个函数 find()，它将接收 s，
如果 parent[s] 等于 s，则：
parent[s] := find(parent[s])
返回 parent[s]
定义一个函数 unionNode()，它将接收 a、b，
x := find(a)，y := find(b)
如果 x 等于 y，则：
parent[x] := y
定义一个数组 ans
定义一个函数 getString()，它将接收 t，
定义一个数组 temp
end := 0
curr := 空字符串
对于 end < t 的大小，更新（将 end 加 1），执行：
如果 t[end] 等于空格，则：
将 curr 插入 temp 的末尾
curr := 空字符串
忽略以下部分，跳到下一次迭代
curr := curr 连接 t[end]
将 curr 插入 temp 的末尾
返回 temp
定义一个函数 dfs()，它将接收字符串 strings、idx、temp（将其初始化为空字符串），
如果 idx 等于 strings 的大小，则：
将 temp 插入 ans 的末尾
返回
current := strings[idx]
如果 color 中不存在 current，则：
dfs(strings, idx + 1, temp + current + ((如果 idx + 1 等于 strings 的大小，则为空字符串，否则为空格)))
否则
定义一个集合 x = groupByColor[color[current]]
对于 x 中的每个元素 z，执行：
dfs(strings, idx + 1, temp + z + ((如果 idx + 1 等于 strings 的大小，则为空字符串，否则为空格)))
（将 z 加 1）
定义一个函数 seeGroups()
对于 groupByColor 中的每个元素 i，执行：
x := i 的第二个元素作为集合
定义一个集合
对于 x 中的每个元素 z：
（将 i 加 1）
定义一个函数 generateSentences()，它将接收一个二维数组 s 和另一个字符串 t，
n := s 的大小
对于 i := 0，当 i < n，更新（将 i 加 1），执行：
x := s[i, 0]
y := s[i, 1]
如果 parent 中不存在 x，则：
如果 parent 中不存在 y，则：
unionNode(x, y)
c := 1
对于 i := 0，当 i < n，更新（将 i 加 1），执行：
x := s[i, 0]
z := s[i, 1]
y := find(x)
如果 color 中不存在 y，则：
color[y] := c
（将 c 加 1）
color[x] := color[y]
color[z] := color[y]
如果 groupByColor 中不存在 color[x]，则：
定义一个集合 ss
将 x 插入 ss
将 y 插入 ss
groupByColor[color[x]] := ss
否则
将 x 插入 groupByColor[color[x]]
将 z 插入 groupByColor[color[x]]
定义一个数组 strings = getString(t)
dfs(strings, 0)
对数组 ans 进行排序
返回 ans
示例
让我们看看以下实现，以便更好地理解：
#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;
}
class Solution {
public:
map <string, string> parent;
map <string, int> color;
map <int, set<string<> groupByColor;
string find(string s){
if(parent[s] == s)return s;
parent[s] = find(parent[s]);
return parent[s];
}
void unionNode(string a, string b){
string x = find(a);
string y = find(b);
if(x == y)return;
parent[x] = y;
}
vector <string< ans;
vector <string< getString(string t){
vector <string< temp;
int end = 0;
string curr = "";
for(;end < t.size(); end++){
if(t[end] == ' '){
temp.push_back(curr);
curr = "";
continue;
}
curr += t[end];
}
temp.push_back(curr);
return temp;
}
void dfs(vector <string< &strings, int idx, string temp = ""){
if(idx == strings.size()){
ans.push_back(temp);
return;
}
string current = strings[idx];
if(color.find(current) == color.end()){
dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" "));
}
else{
set <string< x = groupByColor[color[current]];
set <string< :: iterator z = x.begin();
while(z != x.end()){
dfs(strings, idx + 1, temp + *z + (idx+1 == strings.size()?"":" "));
z++;
}
}
}
void seeGroups(){
map <int, set <string< > :: iterator i = groupByColor.begin();
while(i != groupByColor.end()){
set <string< x = i->second;
set <string< :: iterator z = x.begin();
while(z != x.end()){
z++;
}
cout << endl;
i++;
}
}
vector<string< generateSentences(vector<vector<string<>& s, string t) {
int n = s.size();
for(int i = 0; i < n; i++){
string x = s[i][0];
string y = s[i][1];
if(parent.find(x) == parent.end())parent[x] = x;
if(parent.find(y) == parent.end())parent[y] = y;
unionNode(x,y);
}
int c = 1;
for(int i = 0; i < n; i++){
string x = s[i][0];
string z = s[i][1];
string y = find(x);
if(color.find(y) == color.end()){
color[y] = c;
c++;
}
color[x] = color[y];
color[z] = color[y];
if(groupByColor.find(color[x]) == groupByColor.end()){
set <string< ss;
ss.insert(x);
ss.insert(y);
groupByColor[color[x]] = ss;
}
else{
groupByColor[color[x]].insert(x);
groupByColor[color[x]].insert(z);
}
}
vector <string< strings = getString(t);
dfs(strings, 0);
sort(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
vector<vector<string<> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}};
print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday"));
}输入
[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"
输出
[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday, ]
浏览量：366
