3758. Convert Number Words to Digits 🔒

题目描述

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.

解法

方法一：枚举

我们首先将数字单词与对应的数字建立映射关系，记录在数组 \(d\) 中，其中 \(d[i]\) 表示数字 \(i\) 对应的单词。

然后我们从左到右遍历字符串 \(s\)，对于每个位置 \(i\)，我们依次枚举数字单词 \(d[j]\)，判断从位置 \(i\) 开始的子串是否与 \(d[j]\) 匹配。如果匹配成功，则将数字 \(j\) 添加到结果中，并将位置 \(i\) 向后移动 \(|d[j]|\) 个位置。否则，将位置 \(i\) 向后移动 1 个位置。

我们重复上述过程，直到遍历完整个字符串 \(s\)。最后将结果中的数字连接成字符串并返回。

时间复杂度 \(O(n \times |d|)\)，空间复杂度 \(O(|d|)\)，其中 \(n\) 是字符串 \(s\) 的长度，而 \(|d|\) 是数字单词的数量。

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 🔒

题目描述

解法

方法一：枚举

评论