Chuỗi sắp xếp tùy chỉnh trong C ++

Giả sử chúng ta có S và T là hai chuỗi được tạo bởi các chữ cái viết thường. Trong S, không có chữ cái nào xuất hiện nhiều hơn một lần. S đã được sắp xếp theo một số thứ tự tùy chỉnh trước đó. Chúng ta phải hoán vị các ký tự của T để chúng phù hợp với thứ tự mà S đã được sắp xếp. Cụ thể hơn, nếu x xuất hiện trước y trong S, thì x sẽ xuất hiện trước y trong chuỗi trả về.

Vì vậy, nếu S =“cba” và T =“abcd”, thì đầu ra sẽ là “cbad”. Ở đây "a", "b", "c" xuất hiện trong S, vì vậy thứ tự của "a", "b", "c" phải là "c", "b" và "a". Vì "d" không xuất hiện trong S, nó có thể ở bất kỳ vị trí nào trong T. "dcba", "cdba", "cbda" cũng là các đầu ra hợp lệ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đặt ret thành chuỗi trống

• xác định một bản đồ m và lưu trữ tần số của mỗi ký tự hiện diện trong T thành m

• cho tôi trong phạm vi từ 0 đến kích thước của S - 1

  • x:=S [i]

  • cho j trong khoảng 0 đến m [x] - 1

    • ret:=ret + x

  • m [x]:=0

• cho mỗi cặp nó bằng m -

  • nếu giá trị của nó> 0, thì

    • cho tôi trong phạm vi từ 0 đến giá trị của nó - 1

      • ret:=ret nối khóa của nó

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"cba"
"abcd"

Đầu ra

cbad