leecode423.md

423. 从英文中重建数字

地址:https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/

题目描述

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

示例1

输入：s = "owoztneoer"
输出："012"

示例2

输入：s = "fviefuro"
输出："45"

提示：

• 1 <= s.length <= 105
• s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
• s 保证是一个符合题目要求的字符串

我的解法

没写出来

参考解法

思路

首先我们可以统计每个字母分别在哪些数字中出现：

字母 数字 e 0 1 3 5 7 8 9 f 4 5 g 8 h 3 8 i 5 6 8 9 n 1 7 9 o 0 1 2 4 r 0 3 4 s 6 7 t 2 3 8 u 4 v 5 7 w 2 x 6 z 0

可以发现，z, w, u, x, g 都只在一个数字中，即 0, 2, 4, 6, 80,2,4,6,8 中出现。因此我们可以使用一个哈希表统计每个字母出现的次数，那么 z, w, u, x, g 出现的次数，即分别为0,2,4,6,8 出现的次数。

随后我们可以注意那些只在两个数字中出现的字符：

• h 只在3,8 中出现。由于我们已经知道了 8 出现的次数，因此可以计算出 3 出现的次数。

• f 只在 4,5 中出现。由于我们已经知道了 4 出现的次数，因此可以计算出 5 出现的次数。

• s 只在 6,7 中出现。由于我们已经知道了 6出现的次数，因此可以计算出 7出现的次数。

此时，我们还剩下 1 和 9 的出现次数没有求出：

o 只在0,1,2,4 中出现，由于我们已经知道了0,2,4 出现的次数，因此可以计算出 1出现的次数。 最后的 9 就可以通过 n, i, e 中的任一字符计算得到了。这里推荐使用 i 进行计算，因为 n 在 9 中出现了 2 次，e 在 3 中出现了 2 次，容易在计算中遗漏。

class Solution:
    def originalDigits(self, s: str) -> str:
        c = Counter(s)

        cnt = [0] * 10
        cnt[0] = c["z"]
        cnt[2] = c["w"]
        cnt[4] = c["u"]
        cnt[6] = c["x"]
        cnt[8] = c["g"]

        cnt[3] = c["h"] - cnt[8]
        cnt[5] = c["f"] - cnt[4]
        cnt[7] = c["s"] - cnt[6]
        
        cnt[1] = c["o"] - cnt[0] - cnt[2] - cnt[4]

        cnt[9] = c["i"] - cnt[5] - cnt[6] - cnt[8]

        return "".join(str(x) * cnt[x] for x in range(10))