C++ में लेक्सिकोग्राफिक रूप से सबसे छोटा समतुल्य स्ट्रिंग

मान लीजिए कि हमारे पास समान लंबाई के तार A और B हैं, अब हम कह सकते हैं कि A[i] और B[i] समान वर्ण हैं। तो उदाहरण के लिए, यदि ए ="एबीसी" और बी ="सीडीई", तो हमारे पास 'ए' ='सी', 'बी' ='डी' और 'सी' ='ई' है। समतुल्य वर्ण किसी भी तुल्यता संबंध के सामान्य नियमों का पालन करते हैं:

• रिफ्लेक्सिविटी:'ए' ='ए'

• समरूपता:'ए' ='बी' का अर्थ है 'बी' ='ए'

• ट्रांज़िटिविटी:'ए' ='बी' और 'बी' ='सी' का अर्थ है 'ए' ='सी'

अब उदाहरण के लिए, ऊपर ए और बी से समकक्ष जानकारी दी गई है, एस ="ईड", "एसीडी", और "आब" समकक्ष स्ट्रिंग हैं, और "आब" एस की शब्दावली की सबसे छोटी समकक्ष स्ट्रिंग है। यहां हमें ढूंढना है ए और बी से समकक्ष जानकारी का उपयोग करके एस की शब्दावली के रूप में सबसे छोटी समकक्ष स्ट्रिंग। इस तरह से बनने वाले सभी शब्दों को शब्दावली क्रम में लौटाएं।

तो अगर इनपुट ए ="पार्कर", बी ="मॉरिस" और एस ="पार्सर" जैसा है, तो आउटपुट "मक्केक" होगा। ऐसा इसलिए है क्योंकि ए और बी में समकक्ष जानकारी के आधार पर, हम उनके पात्रों को [एम, पी], [ए, ओ], [के, आर, एस], [ई, आई] के रूप में समूहित कर सकते हैं। तो प्रत्येक समूह में वर्ण समान हैं और शब्दावली क्रम में क्रमबद्ध हैं। तो जवाब है "मक्केक"।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पैरेंट नामक एक सरणी बनाएं

• getParent() नामक एक विधि को परिभाषित करें, यह वर्ण x लेगा

• अगर पैरेंट [x - 'a' का ASCII] -1 है, तो 'a' का x - ASCII लौटाएं

• माता-पिता [x - 'ए' का ASCII]:=getParent ('ए' का ASCII + माता-पिता [x - 'ए' का ASCII])

• वापसी माता-पिता [x - 'ए' का ASCII]

• यूनियन () नामक एक और विधि बनाएं, इसमें ए और बी लगता है

• माता-पिता:=माता-पिता (ए) प्राप्त करें, और माता-पिता:=माता-पिता (बी) प्राप्त करें

• इसलिए यदि माता-पिता =माता-पिता, तो माता-पिता के <माता-पिता, फिर माता-पिता [माता-पिता]:=माता-पिता, और अन्यथा माता-पिता [माता-पिता]:=माता-पिता

• मुख्य विधि से, निम्न कार्य करें -

• पैरेंट सेट करें:=आकार 26 की एक सरणी और -1 का उपयोग करके इसे भरें

• मेरे लिए 0 से 25 की सीमा में

  • प्रदर्शन संघ(ए[i], बी[i])

• एक खाली स्ट्रिंग रिट बनाएं

• मैं के लिए 0 से S के आकार की सीमा में

  • रिट :=रिट + गेटपैरेंट(एस[i]) + 'ए'

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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