資料結構
網路
關係資料庫管理系統 (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
