leetcode 423. Reconstruct Original Digits from English 乱序英文字符串恢复数字 + 发现规律

今天药忘吃喽~ 2022-06-04 09:58 130阅读 0赞

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:  
Input contains only lowercase English letters.  
Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.  
Input length is less than 50,000.  
Example 1:  
Input: “owoztneoer”

Output: “012”  
Example 2:  
Input: “fviefuro”

Output: “45”

本题题意很简单，就是从一个使用英文字符表示的乱序数字字符串中恢复数字，然后排序的问题，本题的核心就是如何恢复数字，这个可以从唯一标志字符来回复，直接看代码吧

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    观察英文单词，six, zero, two, eight, seven, four中分别包含唯一字母x, z, w, g, v, u；因此6, 0, 2, 8, 7, 4需要排在其余数字之前。
    排除这6个数字之后，剩下的4个数字中，按照字母唯一的原则顺次挑选。
    */
    class Solution 
    {
    public:
        string originalDigits(string s) 
        {
            vector<string> words = { "zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine" };
            vector<int> nums = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
            //用以区分的字符
            vector<int> distinct_char = { 'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i' };
            vector<int> counts(26, 0);
            string result;
            for (auto ch : s) { counts[ch - 'a']++; }
            for (int i = 0; i < 10; i++) 
            {
                int count = counts[distinct_char[i] - 'a'];
                for (int j = 0; j < words[i].size(); j++)
                    counts[words[i][j] - 'a'] -= count;
                while (count--)
                    result += to_string(nums[i]);
            }
            sort(result.begin(), result.end());
            return result;
        }
    };