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. Chuỗi T sẽ chứa tất cả các ký tự có trong S, nhưng nó sẽ chứa thêm một ký tự thừa. Nhiệm vụ của chúng ta là tìm ký tự thừa đó bằng một phương pháp hiệu quả.
Để giải quyết bài toán này, chúng ta sẽ lấy một bảng băm rỗng, và chèn tất cả các ký tự của chuỗi thứ hai, sau đó xóa từng ký tự của chuỗi đầu tiên, ký tự còn lại chính 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); }
Kết quả
Extra character: U