Lexicographically สตริงเทียบเท่าที่เล็กที่สุดใน C ++

สมมติว่าเรามีสตริง A และ B ที่มีความยาวเท่ากัน ตอนนี้เราสามารถพูดได้ว่า A[i] และ B[i] เป็นอักขระที่เทียบเท่ากัน ตัวอย่างเช่น ถ้า A ="abc" และ B ="cde" เราก็มี 'a' ='c', 'b' ='d' และ 'c' ='e' อักขระที่เทียบเท่าจะเป็นไปตามกฎปกติของความสัมพันธ์ที่เท่าเทียมกัน:

• การสะท้อนกลับ:'a' ='a'

• สมมาตร:'a' ='b' หมายถึง 'b' ='a'

• Transitivity:'a' ='b' และ 'b' ='c' หมายถึง 'a' ='c'

ตัวอย่างเช่น เมื่อได้รับข้อมูลการสมมูลจาก A และ B ข้างต้น S ="eed", "acd" และ "aab" เป็นสตริงที่เทียบเท่ากัน และ "aab" เป็นสตริงที่เทียบเท่ากับพจนานุกรมที่เล็กที่สุดของ S ที่นี่เราต้องหา สตริงเทียบเท่าพจนานุกรมที่เล็กที่สุดของ S โดยใช้ข้อมูลสมมูลจาก A และ B ส่งกลับคำทั้งหมดที่สามารถเกิดขึ้นได้ในลักษณะนี้ ตามลำดับพจนานุกรม

ดังนั้นหากอินพุตเป็น A ="parker", B ="morris" และ S ="parser" ผลลัพธ์จะเป็น "makkek" เนื่องจากตามข้อมูลเทียบเท่าใน A และ B เราสามารถจัดกลุ่มอักขระเป็น [m,p], [a,o], [k,r,s], [e,i] ดังนั้นอักขระในแต่ละกลุ่มจึงเท่ากันและจัดเรียงตามลำดับศัพท์ คำตอบคือ "มักเคะ"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างอาร์เรย์ที่เรียกว่าพาเรนต์

• กำหนดวิธีการที่เรียกว่า getParent() ซึ่งจะใช้อักขระ x

• ถ้า parent[x – ASCII ของ 'a'] คือ -1 ให้คืนค่า x – ASCII ของ 'a'

• parent[x – ASCII ของ 'a'] :=getParent(ASCII ของ 'a' + parent[x – ASCII ของ 'a'])

• ส่งคืนพาเรนต์[x – ASCII ของ 'a']

• สร้างเมธอดอื่นที่เรียกว่า union() ซึ่งต้องใช้ a และ b

• parentA :=getParent(a) และ parent :=getParent(b)

• ดังนั้น ถ้า parentA =parent ให้คืนค่าเป็นอย่างอื่นเมื่อ parentA

• จากวิธีหลัก ให้ทำดังนี้ −

• ตั้งค่า parent :=อาร์เรย์ขนาด 26 และเติมโดยใช้ -1

• สำหรับผมอยู่ในช่วง 0 ถึง 25

  • ดำเนินการสหภาพ(A[i], B[i])

• สร้างสตริงว่างหนึ่งรายการ

• สำหรับผมอยู่ในช่วง 0 ถึงขนาด S

  • ret :=ret + getParent(S[i]) + ‘a’

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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