Tìm một ký tự thừa trong một chuỗi bằng C ++.

Giả sử chúng ta có hai chuỗi S và T, độ dài của S là n và độ dài của T là n + 1. Chữ T sẽ chứa tất cả các ký tự có mặt trong S, nhưng nó sẽ chứa một ký tự thừa. Nhiệm vụ của chúng tôi là tìm ra nhân vật phụ bằng cách sử dụng một số phương pháp hiệu quả.

Để giải quyết vấn đề này, chúng tôi sẽ lấy một bảng băm trống và chèn tất cả các ký tự của chuỗi thứ hai, sau đó xóa từng ký tự khỏi chuỗi đầu tiên, ký tự còn lại là ký tự thừa.

Ví dụ

#include<iostream>
#include<unordered_map>
using namespace std;
char getExtraCharacter(string S, string T) {
   unordered_map<char, int> char_map;
   for (int i = 0; i < T.length(); i++)
      char_map[T[i]]++;
   for (int i = 0; i < S.length(); i++)
      char_map[S[i]]--;
   for (auto item = char_map.begin(); item != char_map.end(); item++) {
      if (item->second == 1)
      return item->first;
   }
}
int main() {
   string S = "PQRST";
   string T = "TUQPRS";
   cout << "Extra character: " << getExtraCharacter(S, T);
}

Đầu ra

Extra character: U