题目描述
字符串可以用 缩写 进行表示，缩写 的方法是将任意数量的 不相邻 的子字符串替换为相应子串的长度。例如，字符串 "substitution" 可以缩写为（不止这几种方法）：
"s10n" ("s ubstitutio n")"sub4u4" ("sub stit u tion")"12" ("substitution")"su3i1u2on" ("su bst i t u ti on")"substitution" (没有替换子字符串)
下列是不合法的缩写：
"s55n" ("s ubsti tutio n"，两处缩写相邻)"s010n" (缩写存在前导零)"s0ubstitution" (缩写是一个空字符串)
给你一个字符串单词 word 和一个缩写 abbr ，判断这个缩写是否可以是给定单词的缩写。
子字符串是字符串中连续的非空字符序列。
示例 1：
输入：word = "internationalization", abbr = "i12iz4n"
输出：true
解释：单词 "internationalization" 可以缩写为 "i12iz4n" ("i nternational iz atio n") 。
示例 2：
输入：word = "apple", abbr = "a2e"
输出：false
解释：单词 "apple" 无法缩写为 "a2e" 。
提示：
1 <= word.length <= 20word 仅由小写英文字母组成1 <= abbr.length <= 10abbr 由小写英文字母和数字组成abbr 中的所有数字均符合 32-bit 整数范围
解法
方法一：模拟
我们可以直接模拟字符匹配替换。
假设字符串 $word$ 和字符串 $abbr$ 的长度分别为 $m$ 和 $n$，我们使用两个指针 $i$ 和 $j$ 分别指向字符串 $word$ 和字符串 $abbr$ 的初始位置，用一个整型变量 $x$ 记录当前匹配到的 $abbr$ 的数字。
循环匹配字符串 $word$ 和字符串 $abbr$ 的每个字符：
如果指针 $j$ 指向的字符 $abbr[j]$ 是数字，如果 $abbr[j]$ 是 '0'，并且 $x$ 为 $0$，说明 $abbr$ 中的数字含有前导零，因此不是合法的缩写，返回 false；否则将 $x$ 更新为 $x \times 10 + abbr[j] - '0'$。
如果指针 $j$ 指向的字符 $abbr[j]$ 不是数字，那么我们此时将指针 $i$ 往前移动 $x$ 个位置，然后将 $x$ 重置为 $0$。如果此时 $i \geq m$ 或者 $word[i] \neq abbr[j]$，说明两个字符串无法匹配，返回 false；否则将指针 $i$ 往前移动 $1$ 个位置。
然后我们将指针 $j$ 往前移动 $1$ 个位置，重复上述过程，直到 $i$ 超出字符串 $word$ 的长度或者 $j$ 超出字符串 $abbr$ 的长度。
最后，如果 $i + x$ 等于 $m$ 且 $j$ 等于 $n$，说明字符串 $word$ 可以缩写成字符串 $abbr$，返回 true；否则返回 false。
时间复杂度 $O(m + n)$，其中 $m$ 和 $n$ 分别是字符串 $word$ 和字符串 $abbr$ 的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
m, n = len(word), len(abbr)
i = j = x = 0
while i < m and j < n:
if abbr[j].isdigit():
if abbr[j] == "0" and x == 0:
return False
x = x * 10 + int(abbr[j])
else:
i += x
x = 0
if i >= m or word[i] != abbr[j]:
return False
i += 1
j += 1
return i + x == m and j == n
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
int m = word.length(), n = abbr.length();
int i = 0, j = 0, x = 0;
for (; i < m && j < n; ++j) {
char c = abbr.charAt(j);
if (Character.isDigit(c)) {
if (c == '0' && x == 0) {
return false;
}
x = x * 10 + (c - '0');
} else {
i += x;
x = 0;
if (i >= m || word.charAt(i) != c) {
return false;
}
++i;
}
}
return i + x == m && j == n;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public:
bool validWordAbbreviation(string word, string abbr) {
int m = word.size(), n = abbr.size();
int i = 0, j = 0, x = 0;
for (; i < m && j < n; ++j) {
if (isdigit(abbr[j])) {
if (abbr[j] == '0' && x == 0) {
return false;
}
x = x * 10 + (abbr[j] - '0');
} else {
i += x;
x = 0;
if (i >= m || word[i] != abbr[j]) {
return false;
}
++i;
}
}
return i + x == m && j == n;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func validWordAbbreviation(word string, abbr string) bool {
m, n := len(word), len(abbr)
i, j, x := 0, 0, 0
for ; i < m && j < n; j++ {
if abbr[j] >= '0' && abbr[j] <= '9' {
if x == 0 && abbr[j] == '0' {
return false
}
x = x*10 + int(abbr[j]-'0')
} else {
i += x
x = 0
if i >= m || word[i] != abbr[j] {
return false
}
i++
}
}
return i+x == m && j == n
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function validWordAbbreviation(word: string, abbr: string): boolean {
const [m, n] = [word.length, abbr.length];
let [i, j, x] = [0, 0, 0];
for (; i < m && j < n; ++j) {
if (abbr[j] >= '0' && abbr[j] <= '9') {
if (abbr[j] === '0' && x === 0) {
return false;
}
x = x * 10 + Number(abbr[j]);
} else {
i += x;
x = 0;
if (i >= m || word[i++] !== abbr[j]) {
return false;
}
}
}
return i + x === m && j === n;
}
|