fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5. public:
  6.     using u8 = uint8_t;
  7.     using UF = array<u8, 26>;
  8.  
  9.     u8 find(UF& uf, const u8 x) {
  10.         if (uf[x] != x)
  11.         {
  12.             uf[x] = find(uf, uf[x]);
  13.         }
  14.         return uf[x];
  15.     }
  16.  
  17.     u8 const_find(const UF& uf, u8 x) {
  18.         while (uf[x] != x)
  19.         {
  20.             x = uf[x];
  21.         }
  22.         return x;
  23.     }
  24.  
  25.     void merge(UF& uf, u8 a, u8 b) {
  26.         a = find(uf, a);
  27.         b = find(uf, b);
  28.  
  29.         if (a < b)
  30.         {
  31.             uf[b] = a;
  32.         }
  33.         else if (b > a)
  34.         {
  35.             uf[a] = b;
  36.         }
  37.     }
  38.  
  39.     char ch(u8 x) {
  40.         return static_cast<char>(x + 'a');
  41.     }
  42.  
  43.     void print_uf(const UF& uf)
  44.     {
  45.         map<u8, vector<u8>> m;
  46.         for (u8 i = 0; i < uf.size(); ++i)
  47.         {
  48.             const auto f = const_find(uf, i);
  49.             if (f != i)
  50.             {
  51.                 m[f].push_back(i);
  52.             }
  53.         }
  54.  
  55.         for (const auto& [g, els] : m)
  56.         {
  57.             cout << ch(g) << ": \n";
  58.             for (const auto el : els)
  59.             {
  60.                 cout << "  " << ch(el) << "\n";
  61.             }
  62.         }
  63.     }
  64.  
  65.     string smallestEquivalentString(string s1, string s2, string baseStr) {
  66.         UF uf;
  67.         iota(uf.begin(), uf.end(), 0);
  68.  
  69.         for (int i = 0; i < s1.size(); ++i)
  70.         {
  71.             merge(uf, s1[i] - 'a', s2[i] - 'a');
  72.         }
  73.  
  74.         merge(uf, 'p' - 'a', 'm' - 'a');
  75.         print_uf(uf);
  76.  
  77.         for (auto& c : baseStr)
  78.         {
  79.             c = find(uf, c - 'a') + 'a';
  80.         }
  81.         return baseStr;
  82.     }
  83. };
  84.  
  85. int main() {
  86. 	auto sol = Solution{};
  87. 	auto res = sol.smallestEquivalentString("parker", "morris", "parser");
  88. 	cout << res << endl;
  89. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a: 
  o
e: 
  i
k: 
  r
  s
pakkek
https://ideone.com/0WiXTN
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!