Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

Input contains only lowercase English letters.
Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
Input length is less than 50,000.



Example 1:

Input: "owoztneoer"

Output: "012"



Example 2:

Input: "fviefuro"

Output: "45"

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:
class Solution:
    def originalDigits(self, s: str) -> str:
        

Solutions:
class Solution:

	def originalDigits(self, s):
		dmap = {}
		dmap[0] = s.count('z')
		dmap[2] = s.count('w')
		dmap[4] = s.count('u')
		dmap[6] = s.count('x')
		dmap[8] = s.count('g')
		dmap[1] = s.count('o') - dmap[0] - dmap[2] - dmap[4]
		dmap[3] = s.count('h') - dmap[8]
		dmap[5] = s.count('f') - dmap[4]
		dmap[7] = s.count('s') - dmap[6]
		dmap[9] = s.count('i') - dmap[6] - dmap[8] - dmap[5]
		res = ''
		dmap = sorted(list(dmap.items()), key=lambda x: x[0])
		lst = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
		for i in range(len(lst)):
			res += lst[i] * dmap[i][1]
		return res


class Solution:

	def originalDigits(self, s):
		order_c = ['w', 'u', 'x', 'g', 'z', 'o', 't', 'f', 'v', 'i']
		order_d = [2, 4, 6, 8, 0, 1, 3, 5, 7, 9]
		cl = [list(e) for e in ['tow', 'four', 'six', 'eight', 'zero', 'one', 'three', 'five', 'seven', 'nine']]
		digit_cnt = [0] * 10
		counter = dict()
		for c in s:
			counter[c] = counter.get(c, 0) + 1
		for i in range(len(order_c)):
			cnt = counter.get(order_c[i], 0)
			digit_cnt[order_d[i]] = cnt
			if cnt > 0:
				for c in cl[i]:
					counter[c] -= cnt
		ans = list()
		for i in range(len(digit_cnt)):
			if digit_cnt[i] > 0:
				ans.append('%d' % i * digit_cnt[i])
		return ''.join(ans)


class Solution:

	def originalDigits(self, s):
		res = ''
		res += '0' * s.count('z')
		res += '1' * (s.count('o') - s.count('z') - s.count('w') - s.count('u'))
		res += '2' * s.count('w')
		res += '3' * (s.count('h') - s.count('g'))
		res += '4' * s.count('u')
		res += '5' * (s.count('f') - s.count('u'))
		res += '6' * s.count('x')
		res += '7' * (s.count('s') - s.count('x'))
		res += '8' * s.count('g')
		res += '9' * (s.count('i') - s.count('x') - s.count('g') - s.count('f') + s.count('u'))
		return res


class Solution:

	def originalDigits(self, s):
		dump = dict()
		dump[0] = s.count('z')
		dump[2] = s.count('w')
		dump[4] = s.count('u')
		dump[6] = s.count('x')
		dump[8] = s.count('g')
		dump[5] = s.count('f') - dump[4]
		dump[7] = s.count('s') - dump[6]
		dump[3] = s.count('h') - dump[8]
		dump[1] = s.count('o') - dump[0] - dump[2] - dump[4]
		dump[9] = s.count('i') - dump[5] - dump[6] - dump[8]
		tmp = ''
		for i in range(10):
			tmp += str(i) * dump[i]
		return ''.join((letter for letter in sorted(tmp)))


class Solution:

	def originalDigits(self, s):
		d = collections.defaultdict(int)
		for i in s:
			d[i] += 1
		zero = '0' * d['z']
		d['e'] -= d['z']
		d['r'] -= d['z']
		d['o'] -= d['z']
		two = '2' * d['w']
		d['t'] -= d['w']
		d['o'] -= d['w']
		four = '4' * d['u']
		d['f'] -= d['u']
		d['o'] -= d['u']
		d['r'] -= d['u']
		five = '5' * d['f']
		d['i'] -= d['f']
		d['v'] -= d['f']
		d['e'] -= d['f']
		six = '6' * d['x']
		d['s'] -= d['x']
		d['i'] -= d['x']
		seven = '7' * d['v']
		d['s'] -= d['v']
		d['e'] -= d['v'] * 2
		d['n'] -= d['v']
		eight = '8' * d['g']
		d['e'] -= d['g']
		d['i'] -= d['g']
		d['h'] -= d['g']
		d['t'] -= d['g']
		nine = '9' * d['i']
		d['n'] -= d['i'] * 2
		d['e'] -= d['i']
		one = '1' * d['o']
		three = '3' * d['r']
		return zero + one + two + three + four + five + six + seven + eight + nine


class Solution:

	def originalDigits(self, s):
		from collections import Counter
		dic = Counter(s)
		res = {0: '', 1: '', 2: '', 3: '', 4: '', 5: '', 6: '', 7: '', 8: '', 9: ''}
		if dic['z'] != 0:
			res[0] = '0' * dic['z']
			s = s.replace('z', '', dic['z'])
			s = s.replace('e', '', dic['z'])
			s = s.replace('r', '', dic['z'])
			s = s.replace('o', '', dic['z'])
			(dic['z'], dic['e'], dic['r'], dic['o']) = (0, dic['e'] - dic['z'], dic['r'] - dic['z'], dic['o'] - dic['z'])
		if dic['w'] != 0:
			res[2] = '2' * dic['w']
			s = s.replace('t', '', dic['w'])
			s = s.replace('w', '', dic['w'])
			s = s.replace('o', '', dic['w'])
			(dic['t'], dic['w'], dic['o']) = (dic['t'] - dic['w'], 0, dic['o'] - dic['w'])
		if dic['u'] != 0:
			res[4] = '4' * dic['u']
			s = s.replace('f', '', dic['u'])
			s = s.replace('o', '', dic['u'])
			s = s.replace('u', '', dic['u'])
			s = s.replace('r', '', dic['u'])
			(dic['f'], dic['o'], dic['u'], dic['r']) = (dic['f'] - dic['u'], dic['o'] - dic['u'], 0, dic['r'] - dic['u'])
		if dic['x'] != 0:
			res[6] = '6' * dic['x']
			s = s.replace('s', '', dic['x'])
			s = s.replace('i', '', dic['x'])
			s = s.replace('x', '', dic['x'])
			(dic['s'], dic['i'], dic['x']) = (dic['s'] - dic['x'], dic['i'] - dic['x'], 0)
		if dic['g'] != 0:
			res[8] = '8' * dic['g']
			s = s.replace('e', '', dic['g'])
			s = s.replace('i', '', dic['g'])
			s = s.replace('g', '', dic['g'])
			s = s.replace('h', '', dic['g'])
			s = s.replace('t', '', dic['g'])
			(dic['e'], dic['i'], dic['g'], dic['h'], dic['t']) = (dic['e'] - dic['g'], dic['i'] - dic['g'], 0, dic['h'] - dic['g'], dic['t'] - dic['g'])
		if dic['s'] != 0:
			res[7] = '7' * dic['s']
			s = s.replace('s', '', dic['s'])
			s = s.replace('e', '', 2 * dic['s'])
			s = s.replace('v', '', dic['s'])
			s = s.replace('n', '', dic['s'])
			(dic['s'], dic['e'], dic['v'], dic['n']) = (0, dic['e'] - 2 * dic['s'], dic['v'] - dic['s'], dic['n'] - dic['s'])
		if dic['r'] != 0:
			res[3] = '3' * dic['r']
			s = s.replace('t', '', dic['r'])
			s = s.replace('h', '', dic['r'])
			s = s.replace('r', '', dic['r'])
			s = s.replace('e', '', 2 * dic['r'])
			(dic['t'], dic['h'], dic['r'], dic['e']) = (dic['t'] - dic['r'], dic['h'] - dic['r'], 0, dic['e'] - 2 * dic['r'])
		if dic['v'] != 0:
			res[5] = '5' * dic['v']
			s = s.replace('f', '', dic['v'])
			s = s.replace('i', '', dic['v'])
			s = s.replace('v', '', dic['v'])
			s = s.replace('e', '', dic['v'])
			(dic['f'], dic['i'], dic['v'], dic['e']) = (dic['f'] - dic['v'], dic['i'] - dic['v'], 0, dic['e'] - dic['v'])
		if dic['i'] != 0:
			res[9] = '9' * dic['i']
			s = s.replace('n', '', 2 * dic['i'])
			s = s.replace('i', '', dic['i'])
			s = s.replace('e', '', dic['i'])
			(dic['n'], dic['i'], dic['e']) = (dic['n'] - 2 * dic['i'], 0, dic['e'] - dic['i'])
		if dic['n'] != 0:
			res[1] = '1' * dic['n']
			s = s.replace('o', '', dic['n'])
			s = s.replace('n', '', dic['n'])
			s = s.replace('e', '', dic['n'])
			(dic['o'], dic['n'], dic['e']) = (dic['o'] - dic['n'], 0, dic['e'] - dic['n'])
		return res[0] + res[1] + res[2] + res[3] + res[4] + res[5] + res[6] + res[7] + res[8] + res[9]