0%

valid-word-abbreviation

Valid Word Abbreviation – LeetCode 408

Problem

Description

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as “word” contains only the following valid abbreviations:

[“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]

Notice that only the above abbreviations are valid abbreviations of the string “word”. Any other string is not a valid abbreviation of “word”.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool validWordAbbreviation(string word, string abbr) {
int i = 0, j = 0, m = word.size(), n = abbr.size();
while (i < m && j < n) {
if (abbr[j] >= '0' && abbr[j] <= '9') {
if (abbr[j] == '0') return false;
int val = 0;
while (j < n && abbr[j] >= '0' && abbr[j] <= '9') {
val = val * 10 + abbr[j++] - '0';
}
i += val;
} else {
if (word[i++] != abbr[j++]) return false;
}
}
return i == m && j == n;
}
};

思路

简单的双指针循环遍历比较,需要注意的是abbr中的数字可能由多位组成,时间复杂度$O(n)$,空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。