LeetCode 423 Reconstruct Original Digits from English

LeetCode

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order. Example 1:

Input: s = “owoztneoer”
Output: “012”

Example 2:

Input: s = “fviefuro”
Output: “45”

Constraints: 1 <= s.length <= 10<sup>5</sup> s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]. s is *guaranteed to be valid.

题目大意：

数字用英语单词表示如12 -> onetwo, 但打乱顺序otwone. 求如何获得原数字

算法思路：

统计每个字母的个数，根据个数来决定数字
规律见代码： 有些字母但唯一的，如two，w可以知道数字含2
但有些字母是多个数字的和如s，six和seven都含有s，减去用上述的six的个数就知道seven的个数

Python代码：

def originalDigits(self, s: str) -> str:
	char_to_num = {
		'z': '0',
		'w': '2',
		'u': '4',
		'x': '6',
		'g': '8',
		'o': '1',  # decided by previous keys
		'h': '3',  # decided by previous keys
		'f': '5',  # decided by previous keys
		's': '7',  # decided by previous keys
		'i': '9',  # decided by previous keys
	}
	res = []
	char_to_freq = collections.defaultdict(int)
	for char in s:
		char_to_freq[char] += 1
	char_to_freq['o'] -= char_to_freq['z'] + char_to_freq['w'] + char_to_freq['u']
	char_to_freq['h'] -= char_to_freq['g']
	char_to_freq['f'] -= char_to_freq['u']
	char_to_freq['s'] -= char_to_freq['x']
	char_to_freq['i'] -= char_to_freq['x'] + char_to_freq['g'] + char_to_freq['f']
	for char, num in char_to_num.items():
		if char in char_to_freq and char_to_freq[char] > 0:
			for _ in range(char_to_freq[char]):
				res.append(num)
	res.sort()
	return ''.join(res)

算法分析：

时间复杂度为O(10n)，空间复杂度O(n)