Solution For Reconstruct Original Digits From English

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.

Step by Step Implementation For Reconstruct Original Digits From English

public class Solution {
    public String originalDigits(String s) {
        int[] count = new int[10];
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == 'z') count[0]++;
            if (c == 'w') count[2]++;
            if (c == 'x') count[6]++;
            if (c == 's') count[7]++; //7-6
            if (c == 'g') count[8]++;
            if (c == 'v') count[5]++; //5-7
            if (c == 'h') count[3]++; //3-8
            if (c == 'f') count[4]++; //4-5
            if (c == 'i') count[9]++; //9-8-5-6
        }
        count[7] -= count[6];
        count[5] -= count[7];
        count[3] -= count[8];
        count[4] -= count[5];
        count[9] = count[9] - count[8] - count[5] - count[6];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= 9; i++){
            for (int j = 0; j < count[i]; j++){
                sb.append(i);
            }
        }
        return sb.toString();
    }
}

class Solution:
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        # create a dictionary to store the count of each letter
        d = {}
        for c in s:
            d[c] = d.get(c, 0) + 1
        
        # create a list to store the result
        res = []
        
        # helper function to append the digit to the result and update the dictionary
        def appendDigit(digit, d):
            res.append(str(digit))
            for c in str(digit):
                d[c] -= 1
        
        # number of zeros depends on the count of letter 'z'
        appendDigit(0, d)
        
        # number of ones depends on the count of letter 'o'
        appendDigit(1, d)
        
        # number of twos depends on the count of letter 'w'
        appendDigit(2, d)
        
        # number of threes depends on the count of letter 'h'
        appendDigit(3, d)
        
        # number of fours depends on the count of letter 'u'
        appendDigit(4, d)
        
        # number of fives depends on the count of letter 'f'
        appendDigit(5, d)
        
        # number of sixes depends on the count of letter 'x'
        appendDigit(6, d)
        
        # number of sevens depends on the count of letter 's'
        appendDigit(7, d)
        
        # number of eights depends on the count of letter 'g'
        appendDigit(8, d)
        
        # number of nines depends on the count of letter 'i'
        appendDigit(9, d)
        
        # sort the result and return it as a string
        res.sort()
        return "".join(res)

var originalDigits = function(s) {
    // create a hashmap to store the count of each letter
    var map = {};
    for (var i = 0; i < s.length; i++) {
        if (map[s[i]]) {
            map[s[i]]++;
        } else {
            map[s[i]] = 1;
        }
    }
    
    // create an array to store the count of each digit
    var digits = new Array(10).fill(0);
    
    // if a letter only appears in one digit, we can determine the count of that digit
    if (map['z']) {
        digits[0] += map['z'];
        map['e'] -= map['z'];
        map['r'] -= map['z'];
        map['o'] -= map['z'];
        delete map['z'];
    }
    if (map['w']) {
        digits[2] += map['w'];
        map['t'] -= map['w'];
        map['o'] -= map['w'];
        delete map['w'];
    }
    if (map['x']) {
        digits[6] += map['x'];
        map['s'] -= map['x'];
        map['i'] -= map['x'];
        delete map['x'];
    }
    if (map['s']) {
        digits[7] += map['s'];
        map['e'] -= 2 * map['s'];
        map['v'] -= map['s'];
        map['n'] -= map['s'];
        delete map['s'];
    }
    if (map['v']) {
        digits[5] += map['v'];
        map['f'] -= map['v'];
        map['i'] -= map['v'];
        map['e'] -= map['v'];
        delete map['v'];
    }
    if (map['f']) {
        digits[4] += map['f'];
        map['o'] -= map['f'];
        map['u'] -= map['f'];
        map['r'] -= map['f'];
        delete map['f'];
    }
    if (map['r']) {
        digits[3] += map['r'];
        map['t'] -= map['r'];
        map['e'] -= 2 * map['r'];
        map['o'] -= map['r'];
        delete map['r'];
    }
    if (map['o']) {
        digits[1] += map['o'];
        map['n'] -= map['o'];
        map['e'] -= map['o'];
        delete map['o'];
    }
    if (map['t']) {
        digits[8] += map['t'];
        map['e'] -= map['t'];
        map['g'] -= map['t'];
        map['h'] -= map['t'];
        map['i'] -= map['t'];
        delete map['t'];
    }
    if (map['i']) {
        digits[9] += map['i'];
        map['n'] -= 2 * map['i'];
        map['e'] -= map['i'];
        delete map['i'];
    }
    
    // the last digit must be 1
    digits[1] += map['n'];
    
    // convert the array of counts into a string
    var res = '';
    for (var i = 0; i < 10; i++) {
        while (digits[i] > 0) {
            res += i;
            digits[i]--;
        }
    }
    
    return res;
};

The problem can be found here: https://leetcode.com/problems/reconstruct-original-digits-from-english/

One possible solution is as follows:

/*

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"

*/

#include 

#include 

#include 

using namespace std;

class Solution {

public:

string originalDigits(string s) {

unordered_map counts;

for (char c : s) {

counts[c]++;

}

vector nums(10, 0);

// zero

nums[0] = counts['z'];

counts['e'] -= counts['z'];

counts['r'] -= counts['z'];

counts['o'] -= counts['z'];

// two

nums[2] = counts['w'];

counts['t'] -= counts['w'];

counts['o'] -= counts['w'];

// four

nums[4] = counts['u'];

counts['f'] -= counts['u'];

counts['o'] -= counts['u'];

counts['r'] -= counts['u'];

// six

nums[6] = counts['x'];

counts['s'] -= counts['x'];

counts['i'] -= counts['x'];

// eight

nums[8] = counts['g'];

counts['e'] -= counts['g'];

counts['i'] -= counts['g'];

counts['h'] -= counts['g'];

counts['t'] -= counts['g'];

// one

nums[1] = counts['o'];

counts['n'] -= counts['o'];

counts['e'] -= counts['o'];

// three

nums[3] = counts['h'];

counts['t'] -= counts['h'];

counts['r'] -= counts['h'];

counts['e'] -= counts['h'];

counts['e'] -= counts['h'];

// five

nums[5] = counts['f'];

counts['i'] -= counts['f'];

counts['v'] -= counts['f'];

counts['e'] -= counts['f'];

// seven

nums[7] = counts['s'];

counts['e'] -= counts['s'];

counts['v'] -= counts['s'];

counts['e'] -= counts['s'];

counts['n'] -= counts['s'];

// nine

nums[9] = counts['i'];

string res = "";

for (int i = 0; i < 10; i++) {

for (int j = 0; j < nums[i]; j++) {

res += to_string(i);

}

}

return res;

}

};

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            string s = "owoztneoer"; 

            Console.WriteLine(OriginalDigits(s)); 
            Console.ReadLine(); 
        } 

        public static string OriginalDigits(string s) 
        { 
            //The idea is to find out the frequency of each digit from 0 to 9 in the input string s. 
            //Then for each digit, we find out the corresponding letter in the string s. 
            //The letter must be unique to the digit, which means that the letter can only be 
            //associated with one digit. For example, the letter 'z' must be associated with digit 0. 
            //Once we find out a digit, we remove all the occurrences of its corresponding letter in the string s. 

            int[] count = new int[10]; 
            foreach (char c in s) 
            { 
                if (c == 'z') count[0]++; 
                if (c == 'w') count[2]++; 
                if (c == 'x') count[6]++; 
                if (c == 's') count[7]++; //7-6 
                if (c == 'g') count[8]++; 
                if (c == 'u') count[4]++; 
                if (c == 'f') count[5]++; //5-4 
                if (c == 'h') count[3]++; //3-8 
                if (c == 'i') count[9]++; //9-8-5-6 
                if (c == 'o') count[1]++; //1-0-2-4 
            } 
            count[7] -= count[6]; 
            count[5] -= count[4]; 
            count[3] -= count[8]; 
            count[9] = count[9] - count[8] - count[5] - count[6]; 
            count[1] = count[1] - count[0] - count[2] - count[4]; 

            StringBuilder sb = new StringBuilder(); 
            for (int i = 0; i <= 9; i++) 
            { 
                for (int j = 0; j < count[i]; j++) 
                { 
                    sb.Append(i); 
                } 
            } 
            return sb.ToString(); 
        } 
    } 
}