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