Reconstruct Original Digits From English - Leetcode Solution

Problem Statement:

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" Explanation: Zeroes, ones, and twos appear in the input string. "twos" comes before "ones" which comes before "zeroes".

Example 2: Input: "fviefuro" Output: "45"

Solution:

In this problem statement, we are given a non-empty string containing an out-of-order English representation of digits 0-9, and we have to output the digits in ascending order.

We can follow the below approach to solve this problem:

1. We first create an empty dictionary, count, to keep track of the count of each character in the given string.

2. We iterate through the string, s, and for each character, c, we add its count to the count dictionary.

3. We then try to find the count of each digit by checking the presence of certain characters that are unique for each digit.

4. For example, the word "zero" contains only the character 'z', so we can find the count of zeros by checking the count of 'z' in the count dictionary.

5. Similarly, the word "two" contains only the character 'w', so we can find the count of twos by checking the count of 'w' in the count dictionary after removing the count of zeroes from it.

6. Similarly, we can find the count of all the other digits.

7. After this step, we have the count of all the digits, so we can form the output string by iterating through the digits in ascending order and appending the digit to the output string as many times as its count.

8. We return the output string as the final answer.

Below is the Python implementation of the above approach:

class Solution: def originalDigits(self, s: str) -> str: count = {} for c in s: count[c] = count.get(c, 0) + 1

    digits_count = [0] * 10
    digits_count[0] = count.get('z', 0)
    digits_count[2] = count.get('w', 0)
    digits_count[4] = count.get('u', 0)
    digits_count[6] = count.get('x', 0)
    digits_count[8] = count.get('g', 0)
    digits_count[3] = count.get('h', 0) - digits_count[8]
    digits_count[5] = count.get('f', 0) - digits_count[4]
    digits_count[7] = count.get('v', 0) - digits_count[5]
    digits_count[9] = count.get('i', 0) - digits_count[5] - digits_count[6] - digits_count[8]
    digits_count[1] = count.get('n', 0) - digits_count[7] - 2 * digits_count[9]
    
    output = ""
    for i in range(10):
        output += str(i) * digits_count[i]
    
    return output

Time Complexity: O(n)

Space Complexity: O(1)

In this solution, we are using a constant amount of space for the digits_count list and the output string. The time complexity of the solution is also linear as we are iterating through the entire input string only once.

1