หาตัวอักษรเพิ่มเติมหนึ่งตัวในสตริงด้วย C++

สมมติว่าเรามีสตริงสองตัว S และ T ความยาวของ S คือ n และความยาวของ T คือ n + 1 T จะเก็บตัวอักษรทั้งหมดที่มีอยู่ใน S แต่จะมีตัวอักษรเพิ่มเติมอีกหนึ่งตัว ภารกิจของเราคือหาตัวอักษรเพิ่มเติมนั้นโดยใช้วิธีที่มีประสิทธิภาพ

เพื่อแก้ปัญหานี้ เราจะใช้ตารางแฮชว่างหนึ่ง ใส่ตัวอักษรทั้งหมดของสตริงที่สอง แล้วลบตัวอักษรแต่ละตัวของสตริงแรก ตัวอักษรที่เหลือคือตัวอักษรเพิ่มเติม

ตัวอย่างโค้ด

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

ผลลัพธ์

Extra character: U