資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的字典序最小等價字串
假設我們有兩個相同長度的字串 A 和 B，現在我們可以說 A[i] 和 B[i] 是等價字元。例如，如果 A = "abc" 且 B = "cde"，那麼我們有 'a' = 'c'，'b' = 'd' 以及 'c' = 'e'。等價字元遵循任何等價關係的通常規則
自反性：'a' = 'a'
對稱性：'a' = 'b' 意味著 'b' = 'a'
傳遞性：'a' = 'b' 且 'b' = 'c' 意味著 'a' = 'c'
現在，例如，根據上面 A 和 B 中的等價資訊，S = "eed"、"acd" 和 "aab" 是等價字串，而 "aab" 是 S 的字典序最小的等價字串。在這裡，我們必須使用 A 和 B 中的等價資訊來找到 S 的字典序最小的等價字串。返回所有可以透過這種方式形成的單詞，按字典序排序。
因此，如果輸入類似於 A = “parker”，B = “morris” 且 S = “parser”，則輸出將為“makkek”。這是因為根據 A 和 B 中的等價資訊，我們可以將它們的字元分組為 [m,p]、[a,o]、[k,r,s]、[e,i]。因此，每個組中的字元是等價的，並按字典序排序。所以答案是“makkek”。
為了解決這個問題，我們將遵循以下步驟：
建立一個名為 parent 的陣列
定義一個名為 getParent() 的方法，它將接收字元 x
如果 parent[x – ‘a’ 的 ASCII 碼] 為 -1，則返回 x – ‘a’ 的 ASCII 碼
parent[x – ‘a’ 的 ASCII 碼] := getParent(‘a’ 的 ASCII 碼 + parent[x – ‘a’ 的 ASCII 碼])
返回 parent[x – ‘a’ 的 ASCII 碼]
建立另一個名為 union() 的方法，它接收 a 和 b
parentA := getParent(a)，並且 parent := getParent(b)
因此，如果 parentA = parent，則返回；否則，當 parentA < parent 時，parent[parentB] := parentA，否則 parent[parentA] := parent
從主方法中執行以下操作：
將 parent 設定為大小為 26 的陣列，並使用 -1 填充它
對於 i 的範圍從 0 到 25
執行 union(A[i], B[i])
建立一個空字串 ret
對於 i 的範圍從 0 到 S 的大小
ret := ret + getParent(S[i]) + ‘a’
返回 ret
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> parent;
int getParent(char x){
//cout << x << "-- " << x-'a' << endl;
if(parent[x - 'a'] == -1) return x - 'a';
return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
}
void unionn(char a, char b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA == parentB) return;
if(parentA < parentB){
parent[parentB] = parentA;
}else{
parent[parentA] = parentB;
}
}
string smallestEquivalentString(string A, string B, string S) {
parent = vector <int>(26, -1);
for(int i = 0; i < A.size(); i++){
unionn(A[i], B[i]);
}
string ret = "";
for(int i = 0; i < S.size(); i++){
ret += getParent(S[i]) + 'a';
}
return ret;
}
};
main(){
Solution ob;
cout <<
(ob.smallestEquivalentString("parker","morris","parser"));
}輸入
"parker" "morris" "parser"
輸出
makkek
662 次檢視
