跳转至

408. 有效单词缩写 🔒

难度简单

题目描述

字符串可以用 缩写 进行表示，缩写 的方法是将任意数量的 不相邻 的子字符串替换为相应子串的长度。例如，字符串 "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 <= 20
  • word 仅由小写英文字母组成
  • 1 <= abbr.length <= 10
  • abbr 由小写英文字母和数字组成
  • abbr 中的所有数字均符合 32-bit 整数范围

解法

方法一：模拟

思考

缩写由字母与数字交错组成，数字表示跳过的长度，且不能有前导零。若先把缩写展开再比较，数字可能很大，不必真的构造新串。

双指针扫描 \(\textit{abbr}\)：遇数字则累加跳过长度并拒绝前导零；遇字母时先跳过再比对字符。结束时 \(\textit{word}\) 指针加上剩余跳过应恰好到末尾。

跳过与比对必须在同一趟完成，才能同时检查越界、失配与长度是否用尽。

我们可以直接模拟字符匹配替换。

假设字符串 \(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;
}

评论