难度: Medium
给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
示例 1：
输入：s = "owoztneoer" 输出："012"
示例 2：
输入：s = "fviefuro" 输出："45"
提示：
1 <= s.length <= 105s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一s 保证是一个符合题目要求的字符串运行时间: 34 ms
内存: 16.2 MB
class Solution(object):
def originalDigits(self, s):
"""
:type s: str
:rtype: str
"""
ret = ""
nums = [0]*10
nums[0] = s.count("z")
nums[2] = s.count("w")
nums[4] = s.count("u")
nums[6] = s.count("x")
nums[8] = s.count("g")
nums[7] = s.count("s") - nums[6]
nums[5] = s.count("f") - nums[4]
nums[3] = s.count("h") - nums[8]
nums[1] = s.count("o") - nums[0] - nums[2] - nums[4]
nums[9] = s.count("i") - nums[5] - nums[6] - nums[8]
for i in range(0,10):
ret += str(i)*nums[i]
return ret
这个题解的思路是统计字符串中某些独特字母的出现次数，从而推断出对应数字的个数。具体来说： 1. 统计 'z' 的出现次数，推断出 'zero' 即数字 0 的个数 2. 统计 'w' 的出现次数，推断出 'two' 即数字 2 的个数 3. 统计 'u' 的出现次数，推断出 'four' 即数字 4 的个数 4. 统计 'x' 的出现次数，推断出 'six' 即数字 6 的个数 5. 统计 'g' 的出现次数，推断出 'eight' 即数字 8 的个数 6. 统计 's' 的出现次数，减去 'x'('six') 的个数，得到 'seven' 即数字 7 的个数 7. 统计 'f' 的出现次数，减去 'u'('four') 的个数，得到 'five' 即数字 5 的个数 8. 统计 'h' 的出现次数，减去 'g'('eight') 的个数，得到 'three' 即数字 3 的个数 9. 统计 'o' 的出现次数，减去 'z'('zero')、'w'('two')、'u'('four') 的个数，得到 'one' 即数字 1 的个数 10. 统计 'i' 的出现次数，减去 'f'('five')、'x'('six')、'g'('eight') 的个数，得到 'nine' 即数字 9 的个数 最后，按照数字从小到大的顺序，把统计得到的各个数字的个数转化为相应数量的数字字符，拼接成结果字符串返回。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution(object):
def originalDigits(self, s):
"""
:type s: str
:rtype: str
"""
ret = ""
nums = [0]*10
# 统计数字 0 的个数
nums[0] = s.count("z")
# 统计数字 2 的个数
nums[2] = s.count("w")
# 统计数字 4 的个数
nums[4] = s.count("u")
# 统计数字 6 的个数
nums[6] = s.count("x")
# 统计数字 8 的个数
nums[8] = s.count("g")
# 统计数字 7 的个数
nums[7] = s.count("s") - nums[6]
# 统计数字 5 的个数
nums[5] = s.count("f") - nums[4]
# 统计数字 3 的个数
nums[3] = s.count("h") - nums[8]
# 统计数字 1 的个数
nums[1] = s.count("o") - nums[0] - nums[2] - nums[4]
# 统计数字 9 的个数
nums[9] = s.count("i") - nums[5] - nums[6] - nums[8]
# 构造结果字符串
for i in range(0,10):
ret += str(i)*nums[i]
return ret
选择'z', 'w', 'u', 'x', 'g'等字母来首先确定数字的个数是因为这些字母在英文单词中表示数字的拼写中是唯一的。例如，'z'只在'zero'中出现，'w'只在'two'中出现，这样的特性使得它们可以直接确定对应数字的个数，无需考虑其他数字的影响。这种方法提高了算法的效率和准确性。
这样的操作是准确的，不存在误差的可能性。这是因为在确定某些数字的数量时，考虑到一些字母可能同时出现在多个数字的拼写中。例如，'s'既出现在'seven'也出现在'six'中，因此在计算'nums[7]'时需要减去已经确定的'nums[6]'（即'six'的数量）。这种方法确保了每个数字只被计算一次，避免了重复计算。
在实际操作中，减法操作后得到的数字个数不会是负数，因为在执行减法前，已经保证了减数（即'nums[0]', 'nums[2]', 'nums[4]'等）是准确无误的。这些数字的个数是基于独特字母的统计得出的，因此在从总数中减去这些数字的个数时，剩余的数量必然是非负的，这保证了计算的逻辑正确性。
计算数字9的个数时需要减去'nums[5]', 'nums[6]', 'nums[8]'，因为字母'i'出现在'five', 'six', 'eight'和'nine'的拼写中。已经确定的'five', 'six', 和 'eight'的数量中包含了一部分'i'的使用，所以在计算'nine'的数量时，必须减去这些数字中包含的'i'的数量，以确保得到准确的'nine'的个数。这种方法是基于字母'i'在多个数字拼写中共同出现的情况考虑的。