ค้นหาอักขระพิเศษหนึ่งตัวในสตริงโดยใช้ 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