3758. Convert Number Words to Digits 🔒

Description

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.

Solutions

Solution 1: Enumeration

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.

Python3JavaC++GoTypeScript

class Solution:
    def convertNumber(self, s: str) -> str:
        d = [
            "zero",
            "one",
            "two",
            "three",
            "four",
            "five",
            "six",
            "seven",
            "eight",
            "nine",
        ]
        i, n = 0, len(s)
        ans = []
        while i < n:
            for j, t in enumerate(d):
                m = len(t)
                if i + m <= n and s[i : i + m] == t:
                    ans.append(str(j))
                    i += m - 1
                    break
            i += 1
        return "".join(ans)

class Solution {
    public String convertNumber(String s) {
        String[] d
            = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        int n = s.length();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < d.length; ++j) {
                String t = d[j];
                int m = t.length();
                if (i + m <= n && s.substring(i, i + m).equals(t)) {
                    ans.append(j);
                    i += m - 1;
                    break;
                }
            }
        }
        return ans.toString();
    }
}

class Solution {
public:
    string convertNumber(string s) {
        vector<string> d = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        int n = s.length();
        string ans;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < d.size(); ++j) {
                string t = d[j];
                int m = t.length();
                if (i + m <= n && s.substr(i, m) == t) {
                    ans += to_string(j);
                    i += m - 1;
                    break;
                }
            }
        }
        return ans;
    }
};

func convertNumber(s string) string {
    d := []string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}
    n := len(s)
    var ans strings.Builder
    for i := 0; i < n; i++ {
        for j, t := range d {
            m := len(t)
            if i+m <= n && s[i:i+m] == t {
                ans.WriteString(strconv.Itoa(j))
                i += m - 1
                break
            }
        }
    }
    return ans.String()
}

function convertNumber(s: string): string {
    const d: string[] = [
        'zero',
        'one',
        'two',
        'three',
        'four',
        'five',
        'six',
        'seven',
        'eight',
        'nine',
    ];
    const n = s.length;
    const ans: string[] = [];
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < d.length; ++j) {
            const t = d[j];
            const m = t.length;
            if (i + m <= n && s.substring(i, i + m) === t) {
                ans.push(j.toString());
                i += m - 1;
                break;
            }
        }
    }
    return ans.join('');
}

3758. Convert Number Words to Digits 🔒

Description

Solutions

Solution 1: Enumeration

Comments