algoadvance

Leetcode 423. Reconstruct Original Digits from English

Problem Statement

Given a non-empty string containing an out-of-order English representation of digits 0-9, you are to output the digits in ascending order. The English representation of digits ranges from “zero” to “nine”.

Example:

Approach:

You need to find the frequency of each digit from the jumbled string. To simplify the process, certain characters can uniquely identify specific digits.

Clarifying Questions

  1. Input Constraints:
    • Can the string contain characters other than those in the digit words from “zero” to “nine”?

    No, the string will only contain characters from the digit words.

  2. Output Format:
    • Should the output be a string of digits in ascending order?

    Yes.

Strategy

The idea is to count the frequency of certain characters that uniquely identify each digit:

  1. Unique characters:
    • ‘z’ is unique to “zero” (0).
    • ‘w’ is unique to “two” (2).
    • ‘u’ is unique to “four” (4).
    • ‘x’ is unique to “six” (6).
    • ‘g’ is unique to “eight” (8).
  2. Characters identifying the remaining digits:
    • ‘o’ can appear in “zero” (0), “one” (1), “two” (2), “four” (4).
    • ‘h’ can appear in “three” (3), “eight” (8).
    • ‘f’ can appear in “four” (4), “five” (5).
    • ’s’ can appear in “six” (6), “seven” (7).
    • ‘i’ can appear in “five” (5), “six” (6), “eight” (8), “nine” (9).

Steps:

  1. Count occurrences of each character in the string.
  2. Use the unique characters to determine the frequency of their respective digits.
  3. Use these frequencies to adjust and identify the counts of other digits.
  4. Construct the output string.

Code

Here’s a C++ solution implementing the given strategy:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

string originalDigits(string s) {
    vector<int> count(10, 0);
    unordered_map<char, int> freq;
    
    for (char c : s)
        ++freq[c];
    
    // Identifying each digit by unique characters
    count[0] = freq['z'];
    count[2] = freq['w'];
    count[4] = freq['u'];
    count[6] = freq['x'];
    count[8] = freq['g'];
    
    // For the digits that don't have a unique marker, calculate based on remaining counts
    count[3] = freq['h'] - count[8];  // "three" has 'h' and so does "eight"
    count[5] = freq['f'] - count[4];  // "five" has 'f' and so does "four"
    count[7] = freq['s'] - count[6];  // "seven" has 's' and so does "six"
    count[1] = freq['o'] - count[0] - count[2] - count[4];  // "one" has 'o' and so do "zero", "two" and "four"
    count[9] = freq['i'] - count[5] - count[6] - count[8];  // "nine" has 'i' and so do "five", "six", "eight"
    
    // Construct the final result
    string result = "";
    for (int i = 0; i < 10; ++i) {
        result += string(count[i], '0' + i);
    }
    
    return result;
}

int main() {
    string s = "owoztneoer";
    cout << originalDigits(s) << endl;  // Output: "012"
    return 0;
}

Time Complexity

The time complexity of this solution is O(n) where n is the length of the input string. This is because we process each character in the string a constant number of times. The space complexity is also O(1) because the frequency dictionary and digit counters are of fixed size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI