Skip to main content
Talentd

Convert Number Words to Digits - Solution & Explanation

MediumPremiumFree on FleetCodeStringTrie9 min read
Practice this problem

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 <= 105
  • s contains 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumeration with Word MatchingO(n * k)O(1)Simple implementation when the number of possible words is small
Hash Map Incremental ScanO(n)O(1)General case with fast constant-time word lookup
Trie-Based ParsingO(n)O(m)Useful when many word patterns exist or prefix matching is required

Video Solution

Convert Number Words To Digits • Owen Wu • 104 views views

Frequently Asked Questions

Is Convert Number Words to Digits easy or hard?
Convert Number Words to Digits is typically considered a medium difficulty string problem. The main challenge is correctly parsing sequential characters and detecting when a valid number word completes. Once the mapping strategy is clear, the implementation becomes straightforward.
Convert Number Words to Digits Python/Java solution
In Python or Java, create a map from number words to digits and scan the string while building characters in a temporary variable. When the variable matches a key in the map, append the mapped digit to the result and clear the buffer. The same logic translates directly to C++, Go, and TypeScript.
How to solve Convert Number Words to Digits in O(n)?
Maintain a dictionary mapping words like "zero" to "0" and "one" to "1". Iterate through the string and append characters to a temporary buffer. When the buffer matches a number word in the dictionary, append the corresponding digit to the result and reset the buffer. Each character is processed once, giving O(n) time complexity.
What is the best approach for Convert Number Words to Digits?
The most practical solution uses a hash map of number words to digits and scans the string while building characters until a valid word appears. Each match is replaced with its corresponding digit. This approach runs in O(n) time with constant extra space and is easy to implement in interviews.
Is Convert Number Words to Digits asked at Google/Amazon/Meta?
Problems involving parsing number words and converting them to digits appear in interviews that test string parsing and prefix matching. Variants of this problem have appeared in coding interviews at large tech companies such as Amazon and Google where candidates must process textual numbers efficiently.
What data structure is used in Convert Number Words to Digits?
The most common structures are hash maps for constant-time word lookup and Tries for prefix-based matching. A Trie is particularly useful when multiple word patterns share prefixes and the problem requires efficient incremental parsing of characters.
What is the time complexity of Convert Number Words to Digits?
The optimal implementation runs in O(n) time where n is the length of the input string. Each character is processed once while checking whether the current substring forms a valid number word. Space complexity is typically O(1) when only a fixed dictionary of number words is stored.

Ready to solve this problem?

Practice Convert Number Words to Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring