408. 有效单词缩写

English Version

题目描述

字符串可以用 缩写 进行表示，缩写 的方法是将任意数量的 不相邻 的子字符串替换为相应子串的长度。例如，字符串 "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 整数范围

解法

方法一：模拟

模拟字符匹配替换。

同时遍历 $word$ 和 $abbr$，若 $abbr$ 遇到数字，则 $word$ 跳过对应数字长度的字符数。若数字为空，或者有前导零，则提前返回 false。

时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。其中 $m$ 是 $word$ 的长度，而 $n$ 是 $abbr$ 的长度。

Python3

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i = j = 0
        m, n = len(word), len(abbr)
        while i < m:
            if j >= n:
                return False
            if word[i] == abbr[j]:
                i, j = i + 1, j + 1
                continue
            k = j
            while k < n and abbr[k].isdigit():
                k += 1
            t = abbr[j: k]
            if not t.isdigit() or t[0] == '0' or int(t) == 0:
                return False
            i += int(t)
            j = k
        return i == m and j == n

Java

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int m = word.length(), n = abbr.length();
        int i = 0, j = 0;
        while (i < m) {
            if (j >= n) {
                return false;
            }
            if (word.charAt(i) == abbr.charAt(j)) {
                ++i;
                ++j;
                continue;
            }
            int k = j;
            while (k < n && Character.isDigit(abbr.charAt(k))) {
                ++k;
            }
            String t = abbr.substring(j, k);
            if (j == k || t.charAt(0) == '0' || Integer.parseInt(t) == 0) {
                return false;
            }
            i += Integer.parseInt(t);
            j = k;
        }
        return i == m && j == n;
    }
}

C++

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        int m = word.size(), n = abbr.size();
        while (i < m) {
            if (j >= n) {
                return false;
            }
            if (word[i] == abbr[j]) {
                ++i;
                ++j;
                continue;
            }
            int k = j;
            while (k < n && isdigit(abbr[k])) {
                ++k;
            }
            string t = abbr.substr(j, k - j);
            if (k == j || t[0] == '0') {
                return false;
            }
            int x = stoi(t);
            if (x == 0) {
                return false;
            }
            i += x;
            j = k;
        }
        return i == m && j == n;
    }
};

Go

func validWordAbbreviation(word string, abbr string) bool {
	i, j := 0, 0
	m, n := len(word), len(abbr)
	for i < m {
		if j >= n {
			return false
		}
		if word[i] == abbr[j] {
			i++
			j++
			continue
		}
		k := j
		for k < n && abbr[k] >= '0' && abbr[k] <= '9' {
			k++
		}
		if k == j || abbr[j] == '0' {
			return false
		}
		x, _ := strconv.Atoi(abbr[j:k])
		if x == 0 {
			return false
		}
		i += x
		j = k
	}
	return i == m && j == n
}

...