Leetcode 423: Reconstruct Original Digits from English
grid47 Exploring patterns and algorithms
Sep 25, 2024
7 min read
Solution to LeetCode 423: Reconstruct Original Digits from English Problem
You are given a string representing an out-of-order English representation of digits from 0 to 9. Your task is to rearrange the characters of the string in such a way that you can extract the digits in ascending order. The string will only contain valid letters corresponding to the English representations of digits.
Problem
Approach
Steps
Complexity
Input: The input is a string s that contains characters representing the out-of-order English words for digits 0-9.
Example: Input: s = "enionzotwo"
Constraints:
• 1 <= s.length <= 10^5
• s[i] is one of the characters from a predefined set representing the letters in digit words.
• The input string will always be valid and contain only characters from the English digit words.
Output: The output should be a string containing the digits, sorted in ascending order, as a result of extracting the digits from the input string.
Example: Output: "012"
Constraints:
• The output string should contain the digits in ascending order.
Goal: The goal is to extract the digits from the scrambled string based on their English word representations, utilizing the distinct characters in each word to identify and count the digits.
Steps:
• Identify the distinct characters that can be used to determine the presence of certain digits (e.g., 'z' for zero, 'w' for two, etc.).
• Count the occurrences of each character in the input string.
• Using the character counts, determine how many of each digit appears in the string.
• Rebuild the string by adding the digits in ascending order.
Goal: The problem is constrained by the size of the input string and the valid characters it can contain.
Steps:
• The input string has a maximum length of 100,000 characters.
• All characters in the string are part of the set of letters that correspond to the English words for the digits.
Assumptions:
• The input string will always be valid and contain only the necessary letters to form digit words.
• Input: Example 1: Input: s = "owoztneoer"
• Explanation: In this case, the string contains the letters for the words 'zero', 'one', and 'two'. Extracting these gives the digits '0', '1', and '2', resulting in the output "012".
Approach: We solve the problem by counting the occurrences of specific characters that are unique to certain digits. This allows us to determine the number of each digit and then sort them in ascending order.
Observations:
• Certain digits have unique characters that can help identify them (e.g., 'z' for zero, 'w' for two).
• Once we identify and count the digits, we can arrange them in ascending order.
• Using the frequency of characters, we can iteratively determine which digits are present in the string and construct the result.
Steps:
• Initialize a count array for each character in the string.
• Use distinct characters that can uniquely identify digits (e.g., 'z' for 'zero', 'w' for 'two') to find the frequency of each digit.
• For each identified digit, decrement the counts of the characters that make up that digit.
• Repeat the process for all digits and construct the result by appending the corresponding digits.
Empty Inputs:
• The input string will not be empty, as per the constraints.
Large Inputs:
• For large strings with many repeated characters, ensure that the solution is efficient enough to handle the input size.
Special Values:
• Ensure that the solution correctly handles inputs with all digits from 0 to 9.
Constraints:
• The solution should handle inputs with a length up to 100,000 characters efficiently.
This line declares the function `originalDigits`, which accepts a string `s` as input and will return a string containing the digits formed from the characters in `s`.
This vector `distinct_char` contains the distinct characters that help identify each number from 0 to 9 in the string `s`.
5 : Count Array Initialization
vector<int> counts(26, 0);
This initializes a vector `counts` of size 26 to store the frequency of each character in the input string `s`.
6 : Result String Initialization
string result;
A string `result` is initialized to store the final digits that will be returned.
7 : Character Frequency Count
for(autoch : s){ counts[ch-'a']++;}
This loop iterates over each character in the string `s` and increments its corresponding count in the `counts` array.
8 : Main Loop for Digit Construction
for(int i =0; i <10; i++){
This loop iterates over the 10 digits (0-9), processing each one by identifying the number of occurrences of its distinct characters.
9 : Count Extraction
int count = counts[distinct_char[i]-'a'];
This line extracts the count of the distinct character associated with the current digit, which indicates how many times this digit can be formed from `s`.
10 : Character Removal
for(int j =0; j < words[i].size(); j++)
This loop iterates over each character in the corresponding word (e.g., 'zero', 'one') for the current digit.
11 : Character Frequency Update
counts[words[i][j]-'a'] -= count;
This updates the `counts` array by decrementing the frequency of each character in the current digit's word, as those characters are now used.
12 : Digit Addition
while(count--)
This loop adds the current digit to the `result` string as many times as it was identified in the input string `s`.
13 : Result Update
result += to_string(nums[i]);
This line converts the current digit (from `nums[i]`) to a string and appends it to the `result` string.
14 : Result Sorting
sort(result.begin(), result.end());
This sorts the `result` string in ascending order to ensure the digits are returned in a lexicographically sorted order.
15 : Return Statement
return result;
This returns the final string `result`, which contains the digits in sorted order.
Best Case: O(n), where n is the length of the input string.
Average Case: O(n), as we process each character in the string and identify digits in a single pass.
Worst Case: O(n), as the solution requires only a few linear scans over the input string.
Description: The time complexity is linear because we only process the string a constant number of times.
Best Case: O(1), since the space complexity does not depend on the input size.
Worst Case: O(1), as the space used for counting the characters is constant.
Description: The space complexity is constant because we only need a fixed amount of space to store the counts of characters.
