Convert Number Words to Digits

12
2

Problem Statement

You are given a string s containing only lowercase English letters. It may contain the words zero through nine, joined together or mixed with other letters. Return a string containing the digits found while reading s from left to right.

At the current index, check whether a complete number word starts there. If one matches, add its digit to the answer and move past the whole word. Otherwise, skip exactly one character. Letters from a matched word cannot be used again. If no number word is found, return an empty string.

Example 1

Input: s = "zeroonetwo"
Output: "012"
Explanation: Match zero, then one, then two. Their digits form "012".

Example 2

Input: s = "abcthreexfive"
Output: "35"
Explanation: Skip a, b, and c. Match three, skip x, and then match five. The answer is "35".

Brute Force Approach

The string can contain number words such as "one", "two", and "three", along with other characters. To extract the digits, each position in the string can be checked to see whether a number word starts there. Instead of handling every number word separately, all ten words are stored in a list from "zero" to "nine". Their positions in the list give the corresponding digits. For example, "three" is at position 3, so finding "three" means adding '3' to the answer.

A pointer is used to scan the string from left to right. When a number word matches, its digit is added to the answer, and the pointer skips the entire word. If no word matches, the pointer moves to the next character. This way, each matched word is used only once, and the digits remain in the same order as the words appear in the string.

Algorithm

  • Store the number words from "zero" to "nine" in a list, with each word's index representing its digit.

  • Initialize an empty string ans to store the digits and a pointer i to track the current position.

  • Scan the string from left to right until the pointer reaches the end.

  • At each position, check whether any of the ten number words matches the characters starting there.

  • Before comparing a word, check that enough characters are left in the string to form the complete word.

  • If a word matches, add its digit to ans, move the pointer past the matched word, and stop checking other words at that position.

  • If no word matches, move the pointer one position forward.

  • Return ans after the entire string has been scanned.

Dry Run

Convert Number Words to Digits

Convert Number Words to Digits

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Scans the input string left-to-right and extracts number words
string convertNumber(string s) {
// Index of each word directly maps to its numeric digit (0 to 9)
const vector<string> words = {
"zero", "one", "two", "three", "four",
"five", "six", "seven", "eight", "nine"
};
string result;
int i = 0;
while (i < s.size()) {
bool found = false;
for (int digit = 0; digit < 10; digit++) {
const string& word = words[digit];
// Reject a short suffix, then compare here without making a substring.
if (i + word.size() <= s.size() &&
s.compare(i, word.size(), word) == 0) {
// Adding to '0' converts the value 0..9 to its digit character.
result.push_back(char('0' + digit));
// Consume the complete word so its letters cannot be reused.
i += word.size();
found = true;
break;
}
}
// A failed match consumes only the current character.
if (!found) ++i;
}
return result;
}
};
// Driver code
int main() {
Solution sol;
cout << sol.convertNumber("zeroonetwo") << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the input string. For each position, we check at most 10 number words, which takes constant time.

Space Complexity: O(N), the output string could be proportional to the length of the input string.

Optimal Approach

A trie is a tree that stores words one letter at a time. Words with the same beginning share a path. For example, two and three share the first letter t. For details about how to use it, go through this article: Implementation of Trie.

For this problem, we can use a trie data structure to solve it. The last node of each number word stores its digit.

At each starting index i, use another pointer j to follow letters through the trie. A missing path means no number word starts at i. Reaching a node with a digit means a whole word has matched, so append that digit and move i past it.

Keep i unchanged during this lookahead. If the search fails after several letters, only the original starting character is skipped. The trie avoids testing all ten words separately, but both approaches still take O(N) time for this fixed set of short words.

Algorithm

  • Build a trie containing the ten number words from "zero" to "nine". Store each word's corresponding digit at its final node.

  • Create an empty answer string to store the extracted digits and place the first pointer at the beginning of the input string.

  • Continue scanning until the first pointer reaches the end of the string.

  • For each starting position, begin at the root of the trie and place a second pointer at the same position.

  • Use the second pointer to check characters one by one, moving along the matching paths in the trie.

  • If a matching path does not exist, stop searching from the current starting position.

  • If a node containing a digit is reached, add that digit to the answer and move the first pointer past the complete matched word.

  • If no complete number word is found, move the first pointer forward by one character, even if the second pointer matched some letters.

  • Repeat the process until the entire string has been scanned, then return the answer containing the extracted digits in their original order.

Dry Run

Convert Number Words to Digits

Convert Number Words to Digits

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
struct TrieNode {
array<int, 26> children;
int digit;
TrieNode() : digit(-1) {
// -1 indicates the branch doesn't exist
children.fill(-1);
}
};
// Flattened trie using a vector. This is generally faster than
// using pointers (better cache locality) and avoids manual cleanup.
vector<TrieNode> trie;
// Inserts a number word into the trie and tags its final node with the digit.
void insertWord(const string& word, int digit) {
int node = 0;
// Walk through the word and add missing nodes along the path
for (char letter : word) {
int edge = letter - 'a';
int next = trie[node].children[edge];
if (next == -1) {
// Create a new node and link it
next = static_cast<int>(trie.size());
trie[node].children[edge] = next;
trie.emplace_back();
}
node = next; // Move down the tree
}
// Mark the end of the word by saving its actual numeric value
trie[node].digit = digit;
}
public:
Solution() : trie(1) {
// Pre-build the trie with our target words when the class is instantiated
const vector<string> words = {
"zero", "one", "two", "three", "four",
"five", "six", "seven", "eight", "nine"
};
for (int digit = 0; digit < 10; ++digit) {
insertWord(words[digit], digit);
}
}
// Scans left-to-right using the trie to find complete number words
string convertNumber(string s) {
string result;
size_t i = 0;
while (i < s.size()) {
int node = 0;
size_t j = i;
int matchedDigit = -1;
// i stays anchored at the start of our potential word.
// j explores ahead to see if we can trace a valid word in the trie.
while (j < s.size()) {
int next = trie[node].children[s[j] - 'a'];
// Dead end, no word matches this path
if (next == -1) break;
node = next;
++j; // Consume the character
// If we hit a terminal node, we found a valid number word
if (trie[node].digit != -1) {
matchedDigit = trie[node].digit;
break;
}
}
if (matchedDigit != -1) {
// Convert the integer (0-9) to its char equivalent ('0'-'9')
result.push_back(static_cast<char>('0' + matchedDigit));
// Skip 'i' past the word we just consumed to avoid overlaps
i = j;
} else {
// Lookahead failed. Just skip the current character and try again from the next one.
++i;
}
}
return result;
}
};
// Driver code
int main() {
Solution sol;
string s = "zeroonetwo";
cout << sol.convertNumber(s) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), We process the input string once. At each character, we do a limited Trie search that never exceeds the length of the longest word (5 characters).

Space Complexity: O(N+S), S represents the space for the Trie (constant size for digits 0-9), and N represents the memory for the output digit string.

Interview follow-up Questions

No, only 0. The algorithm reads strictly left-to-right. Once it matches "zero", it advances past the entire word, consuming the 'o' and leaving an invalid "ne".

StringTCS NQT

Read Similar Blogs

Comments0