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

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

ตัวอย่าง: S="cba", T="abcd" → "cbad" (ลำดับ a,b,c ตาม S คือ c,b,a ตัว d ไม่อยู่ใน S วางท้ายได้)

ขั้นตอนการแก้ปัญหา

1. นับความถี่ตัวอักษรใน T เก็บใน map m
2. วนตามลำดับ S: ตัวอักษรแต่ละตัว ใส่เข้าผลลัพธ์ตามจำนวนที่มีใน m แล้วเซต m[x] = 0
3. วน map m ที่เหลือ (ตัวไม่อยู่ใน S) ใส่ทุกตัวตามจำนวนที่เหลือ
4. คืนผลลัพธ์

ตัวอย่างโค้ด 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 (char c : T) m[c]++;
        for (char c : S) {
            for (int j = 0; j < m[c]; j++) ret += c;
            m[c] = 0;
        }
        for (auto& [ch, cnt] : m) {
            for (int i = 0; i < cnt; i++) ret += ch;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.customSortString("cba", "abcd");
}

Input

"cba" "abcd"

Output

cbad