C++ Two different versions, based on unique letters


  • 0
    A

    My initial approach. Remove the letters as we process along the dictionary.

    24 / 24 test cases passed
    Status: Accepted
    Runtime: 46 ms

    class Solution {
    public:
        string originalDigits(string s) {
            string res;
            // sequence matters, unique letters must go first
            char dict[10][6] = {"zero", "wto", "ufor", "xis", "geiht", "one", "three", "five", "seven", "inne"};
            char num[10] = {'0', '2', '4', '6', '8', '1', '3', '5', '7', '9'};
            uint hash[26] = {0};
            for (auto c : s) hash[c - 'a']++;
            for (uint i = 0; i < 10; i++) {
                uint cnt = hash[dict[i][0] - 'a'];
                for (uint j = 0, c; c = dict[i][j]; j++) hash[c - 'a'] -= cnt;
                res.insert(res.end(), cnt, num[i]);
            }
            sort(res.begin(), res.end());
            return res;
        }
    };
    

    Optimized for speed version. Skip removing letters and skip sorting.

    24 / 24 test cases passed
    Status: Accepted
    Runtime: 22 ms

    class Solution {
    public:
        string originalDigits(string s) {
            char dict[10] = {'z', 'w', 'u', 'x', 'g', 'o', 't', 'f', 's', 'i'}, num = '0';
            uint hash[26] = {0}, cnt[10];
            for (auto c : s) hash[c - 'a']++;
            for (uint i = 0; i < 10; i++) cnt[i] = hash[dict[i] - 'a'];
            cnt[5] -= cnt[0] + cnt[1] + cnt[2]; // 'o' is shared by zero, one, two, four
            cnt[6] -= cnt[1] + cnt[4]; // 't' is shared by two, three, eight
            cnt[7] -= cnt[2]; // 'f' is shared by four, five
            cnt[8] -= cnt[3]; // 's' is shared by six, seven
            cnt[9] -= cnt[3] + cnt[4] + cnt[7]; // 'i' is shared by six, eight, five, nine
            s.clear();
            for (uint i = 0; i < 10; i++) {
                s.insert(s.end(), cnt[i&1 ? i/2+5 : i/2], num++);
            }
            return s;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.