題目如下：

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"

解題思路：觀察0~9所有的英文表達(dá)，可以發(fā)現(xiàn)有一些字符只會出現(xiàn)一次，例如z只有在zero中有，w在two中有，整理可以得到如下。

　　 #phase 1uniq_dic_1 = {}uniq_dic_1['z'] = ('zero','0')uniq_dic_1['w'] = ('two','2')uniq_dic_1['u'] = ('four','4')uniq_dic_1['x'] = ('six','6')uniq_dic_1['g'] = ('eight','8')

除去這五個單詞后，繼續(xù)尋找只有唯一與眾不同字符的單詞，得到如下。

#phase 2uniq_dic_2 = {}uniq_dic_2['o'] = ('one','1')uniq_dic_2['t'] = ('three', '3')uniq_dic_2['f'] = ('five', '5')uniq_dic_2['s'] = ('seven', '7')

除去上面找到的9個，最后就只剩下nine了。

#phase 3uniq_dic_3 = {}uniq_dic_3['i'] = ('nine', '9')

解題的方法，是先去?phase 1 中找出唯一字符在s中出現(xiàn)了幾次，出現(xiàn)了幾次就表示對應(yīng)的單詞出現(xiàn)了幾次，扣除掉這個單詞其余字符出現(xiàn)的次數(shù)；接下來是phase 2和phase 3，即可得到所有單詞出現(xiàn)的次數(shù)。

代碼如下：

class Solution(object):def calc(self,dic_src,uniq_dic):r = ''for key in uniq_dic.iterkeys():if key in dic_src:count = dic_src[key]r += uniq_dic[key][1] * countfor char in uniq_dic[key][0]:dic_src[char] -= countif dic_src[char] == 0:del dic_src[char]return rdef originalDigits(self, s):""":type s: str:rtype: str"""dic_src = {}for i in s:dic_src[i] = dic_src.setdefault(i, 0) + 1#phase 1uniq_dic_1 = {}uniq_dic_1['z'] = ('zero','0')uniq_dic_1['w'] = ('two','2')uniq_dic_1['u'] = ('four','4')uniq_dic_1['x'] = ('six','6')uniq_dic_1['g'] = ('eight','8')#phase 2uniq_dic_2 = {}uniq_dic_2['o'] = ('one','1')uniq_dic_2['t'] = ('three', '3')uniq_dic_2['f'] = ('five', '5')uniq_dic_2['s'] = ('seven', '7')#phase 3uniq_dic_3 = {}uniq_dic_3['i'] = ('nine', '9')res = ''res += self.calc(dic_src, uniq_dic_1)res += self.calc(dic_src, uniq_dic_2)res += self.calc(dic_src, uniq_dic_3)return ''.join(sorted(list(res)))

?

轉(zhuǎn)載于:https://www.cnblogs.com/seyjs/p/10495443.html

總結(jié)

以上是生活随笔為你收集整理的【leetcode】423. Reconstruct Original Digits from English的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。