หาตัวอักษรที่ไม่ซ้ำกันระหว่างสองสตริงใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ตัวอักษรที่ไม่ซ้ำกัน (uncommon/distinct characters) ระหว่างสองสตริง คือตัวอักษรที่ปรากฏในสตริงใดสตริงหนึ่ง แต่ไม่ปรากฏในอีกสตริงหนึ่ง

ตัวอย่าง

Input: string_one = "tutorialspoint", string_two = "tutorialsworld"
Output: d n p w

อัลกอริทึม: Hashing (Map)

ใช้ map เก็บสถานะของแต่ละตัวอักษร:

• 1 = ปรากฏในสตริงแรกเท่านั้น
• 0 = ปรากฏในทั้งสองสตริง (common)
• 1 (ใหม่) = ปรากฏในสตริงที่สองเท่านั้น

ขั้นตอนการแก้ปัญหา

1. กำหนดสตริงทั้งสอง
2. สร้าง map<char, int> chars
3. วนลูปสตริงแรก: เพิ่มทุกตัวอักษรเข้า map ค่า = 1
4. วนลูปสตริงที่สอง:
   • ถ้ามีใน map แล้ว → ตั้งค่า = 0 (common)
   • ถ้ายังไม่มี → เพิ่มเข้า map ค่า = 1
5. วนลูป map พิมพ์ตัวอักษรที่มีค่า = 1

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

#include <bits/stdc++.h>
#include <map>
using namespace std;

void findDistinctCharacters(string one, string two) {
    map chars;
    
    // สตริงแรก: เพิ่มทุกตัวอักษรค่า 1
    for (int i = 0; i < one.size(); ++i) {
        chars.insert({one[i], 1});
    }
    
    // สตริงที่สอง: อัปเดตสถานะ
    for (int i = 0; i < two.size(); ++i) {
        if (chars.count(two[i])) {
            chars.find(two[i])->second = 0;  // common
        } else {
            chars.insert({two[i], 1});  // ใหม่
        }
    }
    
    // พิมพ์ตัวอักษรที่ไม่ซ้ำ (ค่า = 1)
    for (auto item : chars) {
        if (item.second == 1) {
            cout << item.first << " ";
        }
    }
}

int main() {
    string one = "tutorialspoint";
    string two = "tutorialsworld";
    findDistinctCharacters(one, two);
    return 0;
}

ผลลัพธ์

d n p w

วิธีที่ดีกว่า (ใช้ unordered_set)

void findDistinctSTL(string a, string b) {
    unordered_set setA(a.begin(), a.end());
    unordered_set setB(b.begin(), b.end());
    
    // Symmetric difference
    for (char c : setA) if (!setB.count(c)) cout << c << " ";
    for (char c : setB) if (!setA.count(c)) cout << c << " ";
}

สรุป

ใช้ Hash Map/Set หาตัวอักษรที่ไม่ซ้ำระหว่างสองสตริง O(n+m) เวลา หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ