Convert Number Words To Digits
Convert Number Words to Digits - Video Solution
Watch the video solution for Convert Number Words to Digits, a medium level problem involving String, Trie. This walkthrough by Owen Wu has 104 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string s consisting of lowercase English letters. s may contain valid concatenated English words representing the digits 0 to 9, without spaces.
Your task is to extract each valid number word in order and convert it to its corresponding digit, producing a string of digits.
Parse s from left to right. At each position:
- If a valid number word starts at the current position, append its corresponding digit to the result and advance by the length of that word.
- Otherwise, skip exactly one character and continue parsing.
Return the resulting digit string. If no number words are found, return an empty string.
Example 1:
Input: s = "onefourthree"
Output: "143"
Explanation:
- Parsing from left to right, extract the valid number words "one", "four", "three".
- These map to digits 1, 4, 3. Thus, the final result is
"143".
Example 2:
Input: s = "ninexsix"
Output: "96"
Explanation:
- The substring
"nine"is a valid number word and maps to 9. - The character
"x"does not match any valid number word prefix and is skipped. - Then, the substring
"six"is a valid number word and maps to 6, so the final result is"96".
Example 3:
Input: s = "zeero"
Output: ""
Explanation:
- No substring forms a valid number word during left-to-right parsing.
- All characters are skipped and incomplete fragments are ignored, so the result is an empty string.
Example 4:
Input: s = "tw"
Output: ""
Explanation:
- No substring forms a valid number word during left-to-right parsing.
- All characters are skipped and incomplete fragments are ignored, so the result is an empty string.
Constraints:
1 <= s.length <= 105scontains only lowercase English letters.
Approach Overview
Problem Overview: You receive a string that contains number words such as "zero", "one", "two", and so on. The task is to convert these textual numbers into their digit equivalents while preserving the order in the string. The challenge is identifying valid number words efficiently and replacing them with the corresponding digit characters.
Approach 1: Enumeration with Word Matching (O(n * k) time, O(1) space)
Maintain a mapping from number words to digits (for example "one" → "1", "two" → "2"). Iterate through the string while building a temporary buffer of characters. After each character append, check whether the buffer matches any number word in the dictionary. When a match appears, append the digit to the result and reset the buffer. The factor k represents the number of possible number words checked each time. This approach is straightforward and easy to implement using basic string operations.
Approach 2: Trie-Based Parsing (O(n) time, O(m) space)
Insert all number words into a Trie, where each terminal node stores the corresponding digit. Traverse the input string character by character while walking through the Trie. When a terminal node is reached, append the digit to the result and reset the traversal back to the root. Because each character is processed once and the Trie lookup follows character edges directly, the total complexity becomes linear with respect to the string length. This method avoids repeatedly checking every word candidate.
Approach 3: Greedy Incremental Scan (O(n) time, O(1) space)
Scan the string while gradually building a substring. Each time the substring forms a valid number word in a hash map, output the corresponding digit and clear the substring buffer. Since number words have limited length, the substring remains small and the check is constant time with a hash lookup. This approach behaves like streaming parsing and performs well in practice with minimal memory.
Recommended for interviews: Start with the enumeration or hash-map scanning approach because it clearly demonstrates the parsing idea and keeps the implementation simple. If the interviewer pushes for scalability or structured word matching, the Trie solution shows stronger algorithmic design and familiarity with prefix-based lookup structures often used in string processing problems.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration with Word Matching | O(n * k) | O(1) | Simple implementation when the number of possible words is small |
| Hash Map Incremental Scan | O(n) | O(1) | General case with fast constant-time word lookup |
| Trie-Based Parsing | O(n) | O(m) | Useful when many word patterns exist or prefix matching is required |