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.

Description Hints 1 Solution Video 4:06

3758. Convert Number Words to Digits

Medium67.7% acceptancePremium elsewhere, free here

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 <= 10⁵
s contains only lowercase English letters.

Topics

String Trie

Hints open one at a time

Hint 1

Parse the string from left to right as described, matching against the valid number words

4:06

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

"onefourthree"

Input

"ninexsix"

Input

"zeero"

Input

"tw"

Your code is saved on this device.Solution