423. 从英文中重建数字 | 2022-12-15
我想先统计每个字母出现次数，然后遍历需重建的单词，单词需要什么字母作为原材料，就直接取什么。于是下面代码的复杂性基于这样一个问题：
如果我们打算先重建单词one，建到建不出来为止。但它的字母o在单词two中存在，字母n在单词seven中存在，字母e在单词three中出现。那么重建单词one时是否可能在超支其它单词的字母？
如果我们输入字符串" o n e t w o s e v e n t h r e e " "onetwoseventhree""onetwoseventhree" ，则可能首先重建了两个单词one，然后剩下一堆无法使用的字母。或者说，
是否重建单词本身也可能会有多个正确结果？
接着我对这些单词和它们所包含的字母的分布进行了简单的统计。
| e | g | f | i | h | o | n | s | r | u | t | w | v | x | z |
| 1 | 1 | 1 | ||||||||||||
| 2 | 2 | 2 | ||||||||||||
| 3 | 3 | 3 | 3 | |||||||||||
| 4 | 4 | 4 | 4 |
| 5 | 5 | 5 | 5 | |||||||||||
| 6 | 6 | 6 | ||||||||||||
| 7 | 7 | 7 | 7 |
| 8 | 8 | 8 | 8 | |||||||||||
| 9 | 9 | 9 | ||||||||||||
| 0 | 0 | 0 | 0 |
我发现重建单词可以分为三个批次，分别是{two, four, six, eight, zero}，{one, three, five, seven}， {nine}，如果按照这样的批次顺序去重建单词，上述两个问题就消失了，而同批次的单词之间重建顺序可以是任意的。理由如下：
第一批次中的单词都至少有一个字母是它在这10个单词中独有的，如果这独有的字母还没用完，那必然是还要继续重建那独自占有它的单词。在第一批次结束后，第二批次的单词也都至少有一个字母是它在剩下的6个单词中独有的······
也有其它合适的重建顺序，因为每一次选择重建的单词都可以可能影响后面的选择，而我是在一次选择了一批单词后才进行下一次选择。
如果我们按照三批次的顺序去重建，那么重建结果的排序又成了一个问题，因为我们被要求最后将它们从小到大排序。当然我们可以在重建时先不管顺序，只在最后进行一次排序，但我认为直接进行有序地重建会更快。有序重建只需每次在长度为10的vector<string>中进行查找，而最后排序O ( n ∗ l o g ( n ) ) )是对于 1<=n<=10^5
而言的，桶排序才是最快的，不是吗？
很遗憾我最后的运行时间仅击败了14.98%，那么差距在哪里呢？
//36ms，击败14.98% class Solution { public: string originalDigits(string s) { unordered_map<char, int> hash; string char_list = {'e', 'g', 'f', 'i', 'h', 'o', 'n', 's', 'r', 'u', 't', 'w', 'v', 'x', 'z'}; vector<string> word_list = {"two", "four", "six", "eight", "zero", "one", "three", "five", "seven", "nine"}; vector<string> word_list_sort = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; vector<char> num_list = {'2', '4', '6', '8', '0', '1', '3', '5', '7', '9'}; //字母频率统计 for(auto c : char_list){ hash[c] = 0; } for(auto c : s){ hash[c]++; } //统计每个单词的重建次数 unordered_map<string, int> word_list_count; for(auto num : word_list){ bool flag = true; while(flag){ for(auto c : num){ //这里可能可以优化 if(hash[c] <= 0){ flag = false; } } if(flag == false){ break; } for(auto c : num){ hash[c]--; } word_list_count[num]++; } } //生成数字字符串 string r; for(auto num : word_list_sort){ int it = find(word_list.begin(), word_list.end(), num) - word_list.begin(); int count = word_list_count[num]; for(int i = 0; i < count; i++){ r += num_list[it]; } } return r; } };
