题目描述：

LeetCode 423. Reconstruct Original Digits from English

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

Note:

1. Input contains only lowercase English letters.
2. 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.
3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"

Output: "012"

Example 2:

Input: "fviefuro"

Output: "45"

题目大意：

给定一个非空字符串，包含一组乱序的英文字母表示的数字0-9，按递增序输出这些数字。

注意：

1. 输入只包含小写英文字母
2. 输入确保是有效的，并且一定可以转换为其原始数字。这意味着不会出现"abc", "zerone"之类的非法输入
3. 输入长度小于50000

解题思路：

字符统计 + 枚举

统计字符串s中各字符的个数，需要注意的是，在枚举英文字母时，需要按照特定的顺序方可得到正确答案。

例如按照顺序：6028745913，这个顺序可以类比拓扑排序的过程。

观察英文单词，six, zero, two, eight, seven, four中分别包含唯一字母x, z, w, g, v, u；因此6, 0, 2, 8, 7, 4需要排在其余数字之前。

排除这6个数字之后，剩下的4个数字中，按照字母唯一的原则顺次挑选。

由于剩下的单词中，只有five包含f，因此选为下一个单词；

以此类推，可以得到上面所述的顺序。

Python代码：

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        cnts = collections.Counter(s)
        nums = ['six', 'zero', 'two', 'eight', 'seven', 'four', 'five', 'nine', 'one', 'three']
        numc = [collections.Counter(num) for num in nums]
        digits = [6, 0, 2, 8, 7, 4, 5, 9, 1, 3]
        ans = [0] * 10
        for idx, num in enumerate(nums):
            cntn = numc[idx]
            t = min(cnts[c] / cntn[c] for c in cntn)
            ans[digits[idx]] = t
            for c in cntn:
                cnts[c] -= t * cntn[c]
        return ''.join(str(i) * n for i, n in enumerate(ans))

 

本文链接：http://bookshadow.com/weblog/2016/10/16/leetcode-reconstruct-original-digits-from-english/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码