Reconstruct Original Digits from English

发表于 | 分类于

Reconstruct Original Digits from English

题目描述：

给定一个字符串，其中包含着0~9的英文字符，要求返回其原始的数字字符串。

例子：

具体描述见LeetCode423

解题思路：

主要的思路是在于不同的数字的对应的英文字符串中有各自特殊的字符，比如zero中z字符在其他数字中都不存在。利用这个特点我们可以一一找到各自的数字。思路是我们构建26个字符的统计表；各个数字对应的英文字符串；各个数字以及各个数字对应的特殊的英文字符。然后遍历每个数字，将数字对应的英文字符串的所有字符在统计表中减去；然后根据对应特殊字符的数量来将字符加到结果字符串中即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string originalDigits(string s) {
        vector<string> word = {"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
        vector<char> alpha = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> nums = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        vector<int> counts(26, 0);
        string res;
        for (int i = 0; i < s.size(); i++) counts[s[i] - 'a']++;
        for(int i = 0; i < 10; i++){
            int count = counts[alpha[i] - 'a'];
            for(int j = 0; j < word[i].size(); j++){
                counts[word[i][j] - 'a'] -= count;
            }
            while(count > 0){
                res += to_string(nums[i]);
                count--;
            }
        }
        sort(res.begin(), res.end());
        return res;
        
    }
};