乱序数字单词串提取唯一数字排序的最优O(n)算法求解

问题描述 #

给定一个由0-9对应的英文单词（zero、one……nine）的字符随机打乱组成的字符串，需提取所有存在的数字（每个数字最多保留1个实例），按升序拼接为整数串输出。

• 示例1：输入enenoin，包含one和nine，输出19
• 示例2：输入enenoinone，同样仅统计一次one和nine，输出19

原有贪心解法的缺陷 #

基于数字单词顺序遍历扣减字符的解法严重依赖遍历顺序，顺序选择不当会出现字符误分配的问题：比如输入fonineur时，若优先判定one存在，会占用o、n、e三个字符，导致剩余字符无法匹配原本存在的nine。

O(n)时间复杂度最优解法 #

核心思路 #

利用数字英文单词的字符唯一性特征推导数字存在性，完全避免遍历顺序依赖：

1. 首先统计输入字符串所有字符的出现频次，这一步时间复杂度为O(n)，n为输入字符串长度
2. 观察0-9的英文拼写，部分字符仅在一个数字的单词中出现：
   • z只在zero中出现，只要有z就一定存在数字0
   • w只在two中出现，只要有w就一定存在数字2
   • u只在four中出现，只要有u就一定存在数字4
   • x只在six中出现，只要有x就一定存在数字6
   • g只在eight中出现，只要有g就一定存在数字8
3. 扣除上述5个数字的字符后，剩余字符中又会出现新的唯一特征字符：
   • 剩余的o只属于one（zero、two、four的o已经被扣除）
   • 剩余的h只属于three（eight的h已经被扣除）
   • 剩余的f只属于five（four的f已经被扣除）
   • 剩余的s只属于seven（six的s已经被扣除）
   • 剩余的i只属于nine（five、six、eight的i已经被扣除）
4. 每个数字只要判定存在就只保留1个，因此每次判定存在后仅需要扣减对应单词的各字符1次即可

实现代码 #

import sys
from collections import Counter

# 数字和对应英文单词
num_words = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
# 判定顺序，按特征字符优先级排列
check_order = [
    (0, 'z'), (2, 'w'), (4, 'u'), (6, 'x'), (8, 'g'),
    (1, 'o'), (3, 'h'), (5, 'f'), (7, 's'), (9, 'i')
]

for line in sys.stdin:
    line = line.strip()
    freq = Counter(line)
    exist = [False] * 10
    
    for num, flag_char in check_order:
        if freq.get(flag_char, 0) >= 1:
            exist[num] = True
            # 扣减当前数字单词的所有字符各1次
            for c in num_words[num]:
                freq[c] -= 1
    
    # 拼接升序结果
    res = ''.join(str(i) for i in range(10) if exist[i])
    print(res)

复杂度说明 #

• 时间复杂度：仅需要遍历一次输入字符串统计频次，后续10个数字的判定都是O(1)操作，整体复杂度为O(n)，为理论最优
• 空间复杂度：仅需要存储最多26个英文字母的频次，空间复杂度为O(1)

内容的提问来源于stack exchange，提问作者Zabir Al Nazi Nabil