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.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.
Java
C++
Go
TypeScript
Practice Convert Number Words to Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor