Reconstruct Original Digits from English trong C++

Cho chuỗi chứa các chữ cái lộn xộn của các từ tiếng Anh đại diện cho chữ số 0-9. Khôi phục các chữ số theo thứ tự tăng dần.

Ví dụ: "fviefuro" → "45" (four, five).

Giải thuật (Đếm ký tự đặc trưng)

Mỗi chữ số có ký tự duy nhất:

• z → zero (0)
• w → two (2)
• g → eight (8)
• x → six (6)
• v → five (5) (v chỉ có trong five và seven, nhưng seven có s)
• o → one (1) (o còn trong zero, two, four)
• s → seven (7) (s còn trong six)
• f → four (4) (f còn trong five)
• h → three (3) (h còn trong eight)
• i → nine (9) (i còn trong five, six, eight)

Đếm các ký tự đặc trưng theo thứ tự trên, sau đó trừ đi các ký tự chung.

Ví dụ code

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

class Solution {
public:
    string originalDigits(string s) {
        vector<int> cnt(10);
        for (char c : s) {
            if (c == 'z') cnt[0]++;
            else if (c == 'w') cnt[2]++;
            else if (c == 'g') cnt[8]++;
            else if (c == 'x') cnt[6]++;
            else if (c == 'v') cnt[5]++;
            else if (c == 'o') cnt[1]++;
            else if (c == 's') cnt[7]++;
            else if (c == 'f') cnt[4]++;
            else if (c == 'h') cnt[3]++;
            else if (c == 'i') cnt[9]++;
        }
        cnt[7] -= cnt[6]; // seven - six
        cnt[5] -= cnt[7]; // five - seven
        cnt[4] -= cnt[5]; // four - five
        cnt[1] -= (cnt[0] + cnt[2] + cnt[4]); // one - zero - two - four
        cnt[3] -= cnt[8]; // three - eight
        cnt[9] -= (cnt[5] + cnt[6] + cnt[8]); // nine - five - six - eight
        string ans;
        for (int i = 0; i < 10; i++)
            ans.append(cnt[i], '0' + i);
        return ans;
    }
};

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

Input

"fviefuro"

Output

45