मान लीजिए हमारे पास समान लंबाई की स्ट्रिंग्स 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" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
पैरेंट नामक एक सरणी बनाएं
getParent() नामक एक मेथड परिभाषित करें, यह कैरेक्टर x लेगा
यदि पैरेंट[x - 'a' का ASCII] -1 है, तो x - 'a' का ASCII लौटाएं
पैरेंट[x - 'a' का ASCII] := getParent('a' का ASCII + पैरेंट[x - 'a' का ASCII])
पैरेंट[x - 'a' का ASCII] लौटाएं
union() नामक एक और मेथड बनाएं, यह a और b लेता है
पैरेंटA := getParent(a), और पैरेंट := getParent(b)
इसलिए यदि पैरेंटA = पैरेंट, तो लौटें अन्यथा जब पैरेंटA < पैरेंट, तो पैरेंट[पैरेंटB] := पैरेंटA, और अन्यथा पैरेंट[पैरेंटA] := पैरेंट
मुख्य मेथड से, निम्नलिखित करें:
पैरेंट := आकार 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){ 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