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:
Return the resulting digit string. If no number words are found, return an empty string.
Example 1:
Input: s = "onefourthree"
Output: "143"
Explanation:
"143".Example 2:
Input: s = "ninexsix"
Output: "96"
Explanation:
"nine" is a valid number word and maps to 9."x" does not match any valid number word prefix and is skipped."six" is a valid number word and maps to 6, so the final result is "96".Example 3:
Input: s = "zeero"
Output: ""
Explanation:
Example 4:
Input: s = "tw"
Output: ""
Explanation:
Constraints:
1 <= s.length <= 105s contains only lowercase English letters.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.
We first establish a mapping relationship between number words and their corresponding digits, recorded in array d, where d[i] represents the word corresponding to digit i.
Then we traverse the string s from left to right. For each position i, we enumerate the number words d[j] in order and check whether the substring starting from position i matches d[j]. If a match is found, we add digit j to the result and move position i forward by |d[j]| positions. Otherwise, we move position i forward by 1 position.
We repeat this process until we have traversed the entire string s. Finally, we concatenate the digits in the result into a string and return it.
The time complexity is O(n times |d|) and the space complexity is O(|d|), where n is the length of string s and |d| is the number of digit words.
Python
Java
C++
Go
TypeScript
| 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 |
Convert Number Words To Digits • Owen Wu • 104 views views
Practice Convert Number Words to Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor