【LeetCode每日一题】423. 从英文中重建数字【中等】模拟+哈希

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

示例 1：

输入：s = "owoztneoer" 输出："012" 示例 2：

输入：s = "fviefuro" 输出："45"  

提示：

1 <= s.length <= 105 s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一 s 保证是一个符合题目要求的字符串

题解： 这种题还是非常有意思的，主要在于它很好想，先把这十个英语单词列出来，然后抽丝剥茧一样的先提取出能唯一确定一个单词的字母，比如0（zero）里面的z是十个单词中独有的……

class Solution {
public:
    string originalDigits(string s) {
        unordered_map<char, int> m;
        for(auto e: s){
            m[e]++;
        }
        string ans;
        int cnt = s.size();
        while(cnt){
            while(m['z']){
                m['z']--;
                m['e']--;
                m['r']--;
                m['o']--;
                cnt -= 4;
                ans += '0';
            }
            //cout<<"cnt1:"<<cnt<<endl;
            while(m['w']){
                m['t']--;
                m['w']--;
                m['o']--;
                cnt -= 3;
                ans += '2';
            }
            //cout<<"cnt2:"<<cnt<<endl;
            while(m['u']){
                m['f']--;
                m['o']--;
                m['u']--;
                m['r']--;
                cnt -= 4;
                ans += '4';
            }
            //cout<<"cnt3:"<<cnt<<endl;
            while(m['g']){
                m['e']--;
                m['i']--;
                m['g']--;
                m['h']--;
                m['t']--;
                cnt -= 5;
                ans += '8';
            }
            //cout<<"cnt4:"<<cnt<<endl;
            while(m['x']){
                m['s']--;
                m['i']--;
                m['x']--;
                cnt -= 3;
                ans += '6';
            }
            //cout<<"cnt5:"<<cnt<<endl;
            while(m['r']){
                m['t']--;
                m['h']--;
                m['r']--;
                m['e'] -= 2;
                cnt -= 5;
                ans += '3';
            }
            //cout<<"cnt6:"<<cnt<<endl;
            while(m['f']){
                m['f']--;
                m['i']--;
                m['v']--;
                m['e']--;
                cnt -= 4;
                ans += '5';
            }
            //cout<<"cnt7:"<<cnt<<endl;
            while(m['o']){
                m['o']--;
                m['n']--;
                m['e']--;
                cnt -= 3;
                ans += '1';
            }
            //cout<<"cnt8:"<<cnt<<endl;
            while(m['v']){
                m['s']--;
                m['e'] -= 2;
                m['v']--;
                m['n']--;
                cnt -= 5;
                ans += '7';
            }
            //cout<<"cnt9:"<<cnt<<endl;
            while(m['i']){
                m['n'] -= 2;
                m['i']--;
                m['e']--;
                cnt -= 4;
                ans += '9';
            }
            //cout<<"cnt10:"<<cnt<<endl;
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

官方题解给出的代码看上去更加简洁漂亮一点，要学呀！

class Solution {
public:
    string originalDigits(string s) {
        unordered_map<char, int> c;
        for (char ch: s) {
            ++c[ch];
        }

        vector<int> cnt(10);
        cnt[0] = c['z'];
        cnt[2] = c['w'];
        cnt[4] = c['u'];
        cnt[6] = c['x'];
        cnt[8] = c['g'];

        cnt[3] = c['h'] - cnt[8];
        cnt[5] = c['f'] - cnt[4];
        cnt[7] = c['s'] - cnt[6];

        cnt[1] = c['o'] - cnt[0] - cnt[2] - cnt[4];

        cnt[9] = c['i'] - cnt[5] - cnt[6] - cnt[8];

        string ans;
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                ans += char(i + '0');
            }
        }
        return ans;
    }
};