मान लीजिए हमारे पास दो स्ट्रिंग्स S और T हैं, S की लंबाई n है, और T की लंबाई n+1 है। T में वे सभी वर्ण होंगे जो S में मौजूद हैं, लेकिन इसमें एक अतिरिक्त वर्ण होगा। हमारा कार्य कुछ कुशल दृष्टिकोण का उपयोग करके अतिरिक्त वर्ण ढूंढना है।
इस समस्या को हल करने के लिए, हम एक खाली हैश टेबल लेंगे, और दूसरी स्ट्रिंग के सभी वर्ण डालेंगे, फिर पहली स्ट्रिंग के प्रत्येक वर्ण को हटाएंगे, शेष वर्ण अतिरिक्त वर्ण है।
C++ उदाहरण
#include <iostream>
#include <unordered_map>
using namespace std;
char getExtraCharacter(string S, string T) {
unordered_map 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;
}
return '\0';
}
int main() {
string S = "PQRST";
string T = "TUQPRS";
cout << "Extra character: " << getExtraCharacter(S, T);
return 0;
}
आउटपुट
Extra character: U