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