423. Reconstruct Original Digits from English #

Problem #

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:

Input: "owoztneoer"
Output: "012"

Example 2:

Input: "fviefuro"
Output: "45"

Problem Summary #

Given a non-empty string containing English words representing digits 0-9 with their letters shuffled, output the original digits in ascending order.

Note:

• The input contains only lowercase English letters.
• The input is guaranteed to be valid and can be transformed into the original digits, which means inputs like “abc” or “zerone” are not permitted.
• The input string length is less than 50,000.

Solution Ideas #

• This problem is about finding patterns. First, observe the English words corresponding to 0-9 and find special patterns: all even numbers contain a unique letter:

  z appears only in zero.

  w appears only in two.

  u appears only in four.

  x appears only in six.

  g appears only in eight.

• So first eliminate these even numbers. Then look at the English letters corresponding to the remaining digits. This is also the key to calculating 3, 5, and 7, because some letters appear only in one odd number and one even number (and the even number has already been counted):

  h appears only in three and eight.

  f appears only in five and four.

  s appears only in seven and six.

• Next, only 9 and 0 need to be handled, and the idea is still the same.

  i appears in nine, five, six, and eight.

  n appears in one, seven, and nine.

• Finally, according to the priority above, consume the corresponding English letters in order to generate the final original digits. Note that when converting digits according to priority, pay attention to cases with multiple repeated digits, such as multiple 1s, multiple 5s, and so on.

Code #

package leetcode

import (
	"strings"
)

func originalDigits(s string) string {
	digits := make([]int, 26)
	for i := 0; i < len(s); i++ {
		digits[int(s[i]-'a')]++
	}
	res := make([]string, 10)
	res[0] = convert('z', digits, "zero", "0")
	res[6] = convert('x', digits, "six", "6")
	res[2] = convert('w', digits, "two", "2")
	res[4] = convert('u', digits, "four", "4")
	res[5] = convert('f', digits, "five", "5")
	res[1] = convert('o', digits, "one", "1")
	res[7] = convert('s', digits, "seven", "7")
	res[3] = convert('r', digits, "three", "3")
	res[8] = convert('t', digits, "eight", "8")
	res[9] = convert('i', digits, "nine", "9")
	return strings.Join(res, "")
}

func convert(b byte, digits []int, s string, num string) string {
	v := digits[int(b-'a')]
	for i := 0; i < len(s); i++ {
		digits[int(s[i]-'a')] -= v
	}
	return strings.Repeat(num, v)
}