C ++を使用して、文字列内の1つの余分な文字を検索します。

2つの文字列SとTがあり、Sの長さがnで、Tの長さがn + 1であるとします。TはSに存在するすべての文字を保持しますが、1つの余分な文字を保持します。私たちの仕事は、いくつかの効率的なアプローチを使用して余分なキャラクターを見つけることです。

この問題を解決するために、1つの空のハッシュテーブルを取得し、2番目の文字列のすべての文字を挿入してから、最初の文字列から各文字を削除します。残りの文字は余分な文字です。

例

#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