题目描述

给定一个 非空 字符串，其中包含字母顺序打乱的英文单词表示的数字 0-9。按升序输出原始的数字。

样例

输入："owoztneoer"
输出："012" (zeroonetwo)

输入："fviefuro"
输出："45" (fourfive)

注意

• 输入只包含小写英文字母。
• 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
• 输入字符串的长度小于 50000。

算法

(找规律) $O(n)$

1. 统计每个字母的出现次数。
2. 按照一定顺序枚举待转换的数字。这里的顺序指的是，前者不会由若干个后者拼出。
3. 例如，数字 0 可以放在的第一位，因为 z 只有 0 有。但 1 不可以，因为 one 这三个字母在其他数字中也存在，需要等其他数字都枚举完了之后再枚举 1。
4. 经过检验，0, 2, 4, 1, 3, 5, 6, 7, 8, 9 是一种可行的顺序。
5. 统计出每个数字的个数，按顺序组成答案输出。

时间复杂度

• 每个字符遍历常数次。
• 组装答案时，最多有 $n$ 个数字。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储答案。

C++ 代码

class Solution {
private:
    bool check(const vector<int> &fre, const string &s) {
        for (char c : s)
            if (fre[c - 'a'] == 0)
                return false;
        return true;
    }

    void reduce(vector<int> &fre, const string &s) {
        for (char c : s)
            fre[c - 'a']--;
    }

public:
    string originalDigits(string s) {
        vector<int> fre(26, 0);
        for (char c : s)
            fre[c - 'a']++;

        vector<string> num{"zero", "one", "two", "three", "four",
            "five", "six", "seven", "eight", "nine"};

        vector<int> traversal{0, 2, 4, 1, 3, 5, 6, 7, 8, 9};
        vector<int> res(10, 0);
        for (int d : traversal) {
            while (check(fre, num[d])) {
                res[d]++;
                reduce(fre, num[d]);
            }
        }

        string ans;
        for (int i = 0; i < 10; i++)
            ans += string(res[i], i + '0');

        return ans;
    }
};