LeetCode Solutions Blog

Reconstruct Original Digits from English

Number: 423

Difficulty: Medium

Paid? No

Problem Description

Given a string s containing an out-of-order English representation of digits 0-9, reconstruct the digits and return them in ascending order.

Key Insights

Each digit from 0 to 9 when spelled out contains a unique set of letters.
Some digits contain a letter that doesn't appear in any other digit's spelling; for example, 'z' only appears in "zero".
By counting the occurrence of each letter in s, we can determine the frequency of some digits directly.
The digits that don't have a unique letter must be identified after accounting for overlaps with more unique digits.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(1) since the extra space is used for the fixed size frequency table and result digits.

Solution

We use a frequency table to count each character in the input string. Then, we determine the count of each digit using unique characters in the spelling:

Digit 0: Use the letter 'z' from "zero".
Digit 2: Use the letter 'w' from "two".
Digit 4: Use the letter 'u' from "four".
Digit 6: Use the letter 'x' from "six".
Digit 8: Use the letter 'g' from "eight".

Once these are determined, we can remove their effects from overlapping letters and deduce:

Digit 3: Using the letter 'h' from "three" (after removing eight).
Digit 5: Using the letter 'f' from "five" (after removing four).
Digit 7: Using the letter 's' from "seven" (after removing six).
Digit 1: Using the letter 'o' from "one" (after removing zero, two, and four).
Digit 9: Using the letter 'i' from "nine" (after removing five, six, and eight).

Finally, we form the result string by appending each digit according to its count in ascending order.

Code Solutions

# Python solution with line-by-line comments

def originalDigits(s):
    # Create a frequency dictionary for all characters in s
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Array to hold the frequency of digits 0-9
    digits = [0] * 10

    # Determine the count for digits with unique characters
    digits[0] = char_count.get('z', 0)  # 'z' is unique to "zero"
    digits[2] = char_count.get('w', 0)  # 'w' is unique to "two"
    digits[4] = char_count.get('u', 0)  # 'u' is unique to "four"
    digits[6] = char_count.get('x', 0)  # 'x' is unique to "six"
    digits[8] = char_count.get('g', 0)  # 'g' is unique to "eight"
    
    # For digit 3: 'h' appears in "three" and "eight"
    digits[3] = char_count.get('h', 0) - digits[8]
    # For digit 5: 'f' appears in "five" and "four"
    digits[5] = char_count.get('f', 0) - digits[4]
    # For digit 7: 's' appears in "seven" and "six"
    digits[7] = char_count.get('s', 0) - digits[6]
    # For digit 1: 'o' appears in "one", "zero", "two", "four"
    digits[1] = char_count.get('o', 0) - digits[0] - digits[2] - digits[4]
    # For digit 9: 'i' appears in "nine", "five", "six", and "eight"
    digits[9] = char_count.get('i', 0) - digits[5] - digits[6] - digits[8]
    
    # Build the final output string based on the counts of each digit in ascending order
    result = []
    for digit in range(10):
        result.append(str(digit) * digits[digit])
    
    return ''.join(result)

# Example usage:
print(originalDigits("owoztneoer"))  # Output: "012"
print(originalDigits("fviefuro"))    # Output: "45"