问题描述
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的英文单词打乱顺序后组成。 我们要求的是找出其对应的正确数字，并以升序方式打印
由于不少数字间存在重复字母，因此我们要做的是：先尝试找到能唯一确定某个数字的特征，然后确定该数字数量后，在剩余的字符串中再依次查找其他特征
- 观察后发现，
[z]ero, t[w]o, fo[u]r, si[x]这几个数字可由唯一的字母数量([]标识的字母)； - 在上述数字确定后，以
five为例， 含有f的数字仅有2个，其中four上一步已经确定；因此，从原始字符串中去除上述数字的组成字母后，如果剩余字符串仍然含有f，即表示含有数字five；同理，这一步可由six确定seven，由four确定three - 以上2步完成后，依次类推，可以确定剩余字符串是否含有
one,nine
示例代码
func originalDigits(s string) string {
digitmap := map[string]string{
"zero": "0",
"one": "1",
"two": "2",
"three": "3",
"four": "4",
"five": "5",
"six": "6",
"seven": "7",
"eight": "8",
"nine": "9",
}
ans := []string{}
freq := make(map[rune]int)
for _, v := range s {
freq[v]++
}
// 1. [z]ero, t[w]o, fo[u]r, si[x]
ans = append(ans, decrease(digitmap, freq, "zero", 'z'))
ans = append(ans, decrease(digitmap, freq, "two", 'w'))
ans = append(ans, decrease(digitmap, freq, "four", 'u'))
ans = append(ans, decrease(digitmap, freq, "six", 'x'))
ans = append(ans, decrease(digitmap, freq, "eight", 'g'))
// 2. 确定此时是否含有f, s, r ==> five, seven, three
ans = append(ans, decrease(digitmap, freq, "five", 'f'))
ans = append(ans, decrease(digitmap, freq, "seven", 's'))
ans = append(ans, decrease(digitmap, freq, "three", 'r'))
// 3. 确定此时是否含有o, i ==> one, nine
ans = append(ans, decrease(digitmap, freq, "one", 'o'))
ans = append(ans, decrease(digitmap, freq, "nine", 'i'))
res := []rune(strings.Join(ans, ""))
sort.Slice(res, func(i, j int) bool {
return res[i] < res[j]
})
return string(res)
}
func decrease(digitmap map[string]string, m map[rune]int, number string, digit rune) string {
if m[digit] > 0 {
count := m[digit]
for _, v := range number {
m[v] -= count
}
return strings.Repeat(digitmap[number], count)
}
return ""
}