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

Note:

  1. Input contains only lowercase English letters.
  2. 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.
  3. Input length is less than 50,000.

Example 1:

1
2
Input: "owoztneoer"
Output: "012"

Example 2:

1
2
Input: "fviefuro"
Output: "45"

思路

我们只要找到以下关系即可：

1
2
3
4
5
6
7
8
9
10
zero [构成的字串里只要有一个z，就对应一个0, z <-> 0]
one
two [w <-> 2]
three [除了8之外，只有3有'h']
four [u <-> 4]
five [除了4之外，只有5有'f']
six [x <-> 6]
seven [除了5之外，只有7有'v']
eight [g <-> 8]
nine

剩下的两个数可以同理求出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        stats = {}
        for i in s:
            if (stats.has_key(i)):
                stats[i] += 1
            else:
                stats[i] = 1
        
        res = []
        for i in range(10):
            res.append(0)
            
        res[0] = self.getdictnum(stats, "z")
        res[2] = self.getdictnum(stats, "w")
        res[4] = self.getdictnum(stats, "u")
        res[5] = self.getdictnum(stats, "f") - res[4]
        res[6] = self.getdictnum(stats, "x")
        res[7] = self.getdictnum(stats, "v") - res[5]
        res[8] = self.getdictnum(stats, "g")
        res[3] = self.getdictnum(stats, "h") - res[8]
        res[9] = self.getdictnum(stats, "i") - res[5] - res[6] - res[8]
        res[1] = self.getdictnum(stats, "o") - res[2] - res[0] - res[4]
        
        ans = []
        
        for i, enum in enumerate(res):
            for p in range(enum):
                ans.append(i)
                
        return "".join(str(x) for x in ans)
        
    def getdictnum(self, stats, i):
        if (stats.has_key(i)):
            return stats[i]
        else:
            return 0