สตริงการเรียงลำดับแบบกำหนดเองใน C++

สมมติว่าเรามี S และ T สองสตริงที่ประกอบด้วยตัวอักษรพิมพ์เล็ก ใน S ไม่มีตัวอักษรเกิดขึ้นมากกว่าหนึ่งครั้ง S ถูกจัดเรียงตามลำดับที่กำหนดเองก่อนหน้านี้ เราต้องเปลี่ยนอักขระของ T เพื่อให้ตรงกับลำดับที่ S ถูกจัดเรียง โดยเฉพาะอย่างยิ่ง ถ้า x เกิดขึ้นก่อน y ใน S ดังนั้น x จะเกิดขึ้นก่อน y ในสตริงที่ส่งคืน

ดังนั้นหาก S =“cba” และ T =“abcd” ผลลัพธ์จะเป็น “cbad” ที่นี่ "a", "b", "c" ปรากฏใน S ดังนั้นลำดับของ "a", "b", "c" ควรเป็น "c", "b" และ "a" เนื่องจาก "d" ไม่ปรากฏใน S จึงอาจอยู่ที่ตำแหน่งใดก็ได้ใน T "dcba", "cdba", "cbda" ก็เป็นเอาต์พุตที่ถูกต้องเช่นกัน

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

• ตั้งค่า ret เป็นสตริงว่าง

• กำหนดแผนที่ m และเก็บความถี่ของอักขระแต่ละตัวที่มีอยู่ใน T เป็น m

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

  • x :=S[i]

  • สำหรับ j ในช่วง 0 ถึง m[x] – 1

    • ret :=ret + x

  • ม[x] :=0

• สำหรับแต่ละคู่ในหน่วย m -

  • ถ้าค่าของมันคือ> 0 แล้ว

    • สำหรับฉันอยู่ในช่วง 0 ถึงค่าของมัน – 1

      • ret :=ret เชื่อมคีย์ของมัน

• รีเทิร์น

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string customSortString(string S, string T) {
      string ret = "";
      unordered_map <char, int> m;
      for(int i = 0; i < T.size(); i++){
         m[T[i]]++;
      }
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         for(int j = 0; j < m[x]; j++){
            ret += x;
         }
         m[x] = 0;
      }
      unordered_map <char, int> :: iterator it = m.begin();
      while(it != m.end()){
         if(it->second > 0){
            for(int i = 0; i < it->second; i++)ret += it->first;
         }
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.customSortString("cba", "abcd"));
}

อินพุต

"cba"
"abcd"

ผลลัพธ์

cbad