423. 从英文中重建数字 | 2022-12-15

我想先统计每个字母出现次数，然后遍历需重建的单词，单词需要什么字母作为原材料，就直接取什么。于是下面代码的复杂性基于这样一个问题：

如果我们打算先重建单词one，建到建不出来为止。但它的字母o在单词two中存在，字母n在单词seven中存在，字母e在单词three中出现。那么重建单词one时是否可能在超支其它单词的字母？

如果我们输入字符串"onetwoseventhree""onetwoseventhree""onetwoseventhree" ，则可能首先重建了两个单词one，然后剩下一堆无法使用的字母。或者说，

是否重建单词本身也可能会有多个正确结果？

接着我对这些单词和它们所包含的字母的分布进行了简单的统计。

我发现重建单词可以分为三个批次，分别是{two, four, six, eight, zero}，{one, three, five, seven}， {nine}，如果按照这样的批次顺序去重建单词，上述两个问题就消失了，而同批次的单词之间重建顺序可以是任意的。理由如下：

第一批次中的单词都至少有一个字母是它在这10个单词中独有的，如果这独有的字母还没用完，那必然是还要继续重建那独自占有它的单词。在第一批次结束后，第二批次的单词也都至少有一个字母是它在剩下的6个单词中独有的······

也有其它合适的重建顺序，因为每一次选择重建的单词都可以可能影响后面的选择，而我是在一次选择了一批单词后才进行下一次选择。

如果我们按照三批次的顺序去重建，那么重建结果的排序又成了一个问题，因为我们被要求最后将它们从小到大排序。当然我们可以在重建时先不管顺序，只在最后进行一次排序，但我认为直接进行有序地重建会更快。有序重建只需每次在长度为10的vector中进行查找，而最后排序O(n∗log(n))O(n*log(n))O(n∗log(n))是对于1<=n<=1051<=n<=10^51<=n<=105而言的，桶排序才是最快的，不是吗？

很遗憾我最后的运行时间仅击败了14.98%，那么差距在哪里呢？

//36ms，击败14.98%
class Solution {
public:string originalDigits(string s) {unordered_map hash;string char_list = {'e', 'g', 'f', 'i', 'h', 'o', 'n', 's', 'r', 'u', 't', 'w', 'v', 'x', 'z'};vector word_list = {"two", "four", "six", "eight", "zero", "one","three", "five", "seven", "nine"};vector word_list_sort = {"zero", "one", "two", "three", "four", "five","six", "seven", "eight", "nine"};vector 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 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;}
};

完