Reconstruct Original Digits from English ใน C++

โจทย์: Reconstruct Original Digits from English

ให้สตริงที่ประกอบด้วยตัวอักษรอังกฤษสับสนของคำอ่านตัวเลข 0-9 (zero, one, two, three, four, five, six, seven, eight, nine) ต้องคืนค่าตัวเลขเดิมเรียงจากน้อยไปมาก

ตัวอย่าง: s = "fviefuro" → มีตัวอักษรของ five (5) และ four (4) → ผลลัพธ์: "45"

อัลกอริทึม: Unique Character Identification

บางตัวเลขมีตัวอักษรที่ ไม่ปรากฏในตัวเลขอื่น (unique letters) สามารถนับจำนวนตัวเลขนั้นได้ทันที:

หลังนับ 5 ตัวนี้แล้ว ลบตัวอักษรที่ใช้ออก (หรือลบจำนวนออกจาก count อื่น) แล้วหาตัวเลขที่เหลือ:

ลำดับที่ถูกต้อง (standard solution):

1. นับ z → 0, w → 2, u → 4, x → 6, g → 8
2. นับ h → 3 (three มี h, eight มี h แต่ eight นับแล้ว → ลบ count[8])
3. นับ f → 5 (five มี f, four มี f แต่ four นับแล้ว → ลบ count[4])
4. นับ s → 7 (seven มี s, six มี s แต่ six นับแล้ว → ลบ count[6])
5. นับ o → 1 (one มี o, zero/two/four มี o → ลบ count[0]+count[2]+count[4])
6. นับ i → 9 (nine มี i, five/six/eight มี i → ลบ count[5]+count[6]+count[8])

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

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

class Solution {
public:
    string originalDigits(string s) {
        vector<int> cnt(10, 0);
        
        // นับตัวอักษร unique ก่อน
        for (char c : s) {
            if (c == 'z') cnt[0]++;
            else if (c == 'w') cnt[2]++;
            else if (c == 'u') cnt[4]++;
            else if (c == 'x') cnt[6]++;
            else if (c == 'g') cnt[8]++;
            else if (c == 'h') cnt[3]++; // three, eight
            else if (c == 'f') cnt[5]++; // five, four
            else if (c == 's') cnt[7]++; // seven, six
            else if (c == 'o') cnt[1]++; // one, zero, two, four
            else if (c == 'i') cnt[9]++; // nine, five, six, eight
        }
        
        // ปรับลบตัวที่นับซ้ำ
        cnt[3] -= cnt[8]; // h: three - eight
        cnt[5] -= cnt[4]; // f: five - four
        cnt[7] -= cnt[6]; // s: seven - six
        cnt[1] -= (cnt[0] + cnt[2] + cnt[4]); // o: one - zero - two - four
        cnt[9] -= (cnt[5] + cnt[6] + cnt[8]); // i: nine - five - six - eight
        
        // สร้างผลลัพธ์
        string ans;
        for (int i = 0; i <= 9; i++) {
            ans.append(cnt[i], '0' + i);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.originalDigits("fviefuro") << endl;
    return 0;
}

Input

"fviefuro"

Output

"45"

ความซับซ้อน (Complexity)

• เวลา: O(n) - วนลูปนับตัวอักษร 1 รอบ
• พื้นที่: O(1) - array ขนาดคงที่

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับมีลำดับการลบผิด (cnt[7] -= cnt[6] ก่อน cnt[5] -= cnt[7] ทำให้ cnt[5] ลบค่าผิด) ได้จัดลำดับใหม่ให้ถูกต้องตาม dependency graph

Longest Repeating Character Replacement ใน C++

Partition Equal Subset Sum ใน C++