题目描述
给定一个由小写英文字母组成的字符串 s。s 可能包含表示数字 0 到 9 的 有效连续 英文单词，没有空格。
你的任务是 按顺序 提取 每个 有效的数字词，并将其转换为相应的数字，生成一个数字字符串。
从左往右解析 s。在每个位置：
- 如果当前位置有一个有效的数字单词，将其对应的数字添加到结果中，并将位置向前移动该单词的长度。
- 否则，跳过 恰好 一个字符，继续解析。
返回结果数字字符串。如果没有找到数字单词，返回空字符串。
示例 1：
输入：s = "onefourthree"
输出："143"
解释：
- 从左到右解析，提取有效的数字词 "one"，"four"，"three"。
- 他们映射到数字 1，4，3。因此，最终结果是
"143"。
示例 2：
输入：s = "ninexsix"
输出："96"
解释：
- 子字符串
"nine" 是一个合法的数字词，映射到 9。 - 字符
"x" 没有对应任何有效数字词的前缀，被跳过。 - 然后，子字符串
"six" 是一个有效的数字词并且被映射到 6，所以最后结果是 "96"。
示例 3：
输入：s = "zeero"
输出：""
解释：
- 在从左到右解析过程中，没有任何子串构成有效的数字词。
- 所有字符都被跳过，不完整的片段被忽略，因此结果是空字符串。
示例 4：
输入：s = "tw"
输出：""
解释：
- 在从左到右解析过程中，没有任何子串构成有效的数字词。
- 所有字符都被跳过，不完整的片段被忽略，因此结果是空字符串。
提示：
1 <= s.length <= 105s 只包含小写英文字母。
解法
方法一：枚举
我们首先将数字单词与对应的数字建立映射关系，记录在数组 \(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|\) 是数字单词的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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()
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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('');
}
|