[数据结构与算法][LeetCode解题报告] 423. 从英文中重建数字

一、 题目

1. 题目描述

423. 从英文中重建数字

难度：中等

给你一个字符串 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 保证是一个符合题目要求的字符串

2. 原题链接

链接: 423. 从英文中重建数字

二、 解题报告

1. 思路分析

 有趣的一道题，刚拿到手会没有思路。
 这题我保留了部分没用的注释，但这部分体现了我的思考过程。

• 题目保证是合法字符串，首先会想到要统计每个字符出现的次数然后dfs枚举每个单词去尝试。看了眼数据范围1e5明显是不可以的。
• 即使是dfs枚举每个单词也要统计每个单词中，每个字符出现的次数。
• 统计每个单词的长度有什么意义吗？好像是没用的。
• 然后出现了新的思路：某个字符是否只存在于唯一一个单词里呢，比如z，只出现在zero(0)里，那么s中z的次数就是zero出现的次数！
• 因此出现了我注释中最重要的统计：计算每个字符在哪些单词中出现过，并按出现次数排序，结果是这样的：
• [('z', {0}), ('w', {2}), ('u', {4}), ('x', {6}), ('g', {8}), ('h', {8, 3}), ('f', {4, 5}), ('v', {5, 7}), ('s', {6, 7}), ('r', {0, 3, 4}), ('n', {1, 9, 7}), ('t', {8, 2, 3}), ('o', {0, 1, 2, 4}), ('i', {8, 9, 5, 6}), ('e', {0, 1, 3, 5, 7, 8, 9})]
• 不太好看，我打个表：

• 有了这个表，我们发现z w u x g，都只在某一个单词里出现过，那么在字符串s中统计这些字符出现的次数，就等于它们对应的单词出现的次数。
• 这5个单词分别是z:0,w:2,u:4,x:6,g:8。
• 剩下的怎么办呢，我们继续向下观察这个表，h这行，h只出现在8和3里。而8的数量我们是可以知道的，等于g出现的次数，那么我只需要预先处理g，把8对应的所有字符都减去对应的数量(意味着s中不存在8了)，等同于h只能出现在3里，那么h也可以求出来了。
• 同理继续向下处理，一直处理完v都是没问题的。最后剩个1和9不能用n来代表，因为他们同时出现在n中，继续向后找，发现o中除了1都处理过了，那就用i来代表1，剩下一个i来代表9.
• 把这个表打出来即可。剩下的就是编码。
• 实际上用Counter甚至麻烦了，官解里不预处理减法，直接更新答案的时候减一下，更快一些。

2. 复杂度分析

最坏时间复杂度O(n×10)，n是s的长度，10是一共10个单词，单词长度最多是5，忽略这个常数。

3. 代码实现

打表。

words = [
            'zero','one','two','three','four',
            'five','six','seven','eight','nine'
        ]
cnts = [Counter(w) for w in words]
# lens = defaultdict(list)
# for w in words:
#     lens[len(w)].append(w)

# c_times = defaultdict(set)
# for i,w in enumerate(words):
#     for c in w:
#         c_times[c].add(i)
# c_times_list = sorted(c_times.items(),key = lambda x:len(x[1]))
# print(c_times_list)
orders = [
    ('z',0),
    ('w',2),
    ('u',4),
    ('x',6),
    ('g',8),
    ('h',3),
    ('f',5),
    ('v',7),
    ('o',1),
    ('i',9)
]
class Solution:
    def originalDigits(self, s: str) -> str:       
        cs = Counter(s)
        ans = [0] * 10       
        for c,n in orders:
            # print(cs)
            ans[n] = cs[c]
            for _ in range(ans[n]):
                cs -= cnts[n]
        # print(ans)
        ret = []
        for i,v in enumerate(ans):
            ret.extend([i]*v)
        return ''.join(map(str,ret))                   

三、 本题小结

1. 脑筋急转弯题要多研究一会。