Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
Example 1:
Input: s = "owoztneoer" Output: "012"
Example 2:
Input: s = "fviefuro" Output: "45"
Constraints:
1 <= s.length <= 105s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].s is guaranteed to be valid.This approach uses unique identifiers for each digit's word representation in the English language. By identifying letters present in only one digit's name, like 'z' in 'zero', we progressively remove identified digits from the input string. This allows easy recovery of digits based on the frequency of unique letters.
The solution uses a Counter to keep track of the occurrences of each character in the input string s. It exploits unique characters in the spelling of certain numbers (like 'z' in zero, 'w' in two, etc.) to determine the count of those numbers. After these numbers are found, the script uses overlapping characters to determine others and constructs the result.
Java
Time Complexity: O(n), where n is the length of the string s, since we iterate over the input string and perform constant-time operations using the Counter.
Space Complexity: O(1), as the count array and resultant digit storage both use fixed space not growing with input size.
In this approach, we iteratively subtract recognized digits from the current string until the string is fully reduced. This involves pattern matching for each unique digit using substring searches that account for unique spellings.
This C solution proceeds by implementing character frequency counting similar to former strategies. It builds the result string by appending known digits based on zero-indexed character discovery, leveraging array positions for fast access. Memory management is handled manually to construct a resultant char array.
JavaScript
Time Complexity: O(n) for analyzing the string and constructing the output.
Space Complexity: O(1) since it uses fixed-size data structures for all computational logic without dynamic extensive allocation.
| Approach | Complexity |
|---|---|
| Unique Character Mapping | Time Complexity: O(n), where n is the length of the string |
| Iterative Subtraction | Time Complexity: O(n) for analyzing the string and constructing the output. |
Reconstruct Original Digits from English | Live Coding with Explanation | Leetcode - 423 • Algorithms Made Easy • 5,856 views views
Watch 9 more video solutions →Practice Reconstruct Original Digits from English with our built-in code editor and test cases.
Practice on FleetCode