这个题目给了我们一个单词和一个缩写，我们的任务是检查这个缩写是否能够从原始单词中生成。对于一些简单的缩写，我们可能觉得没啥难度，但要处理复杂的情况，就需要我们动点脑筋了。
题目描述
我们需要设计一个函数，判断一个字符串是否是另一个字符串的有效缩写。有效的缩写指的是，单词中的字母可以不按顺序跳过，但缩写中的字母顺序不能改变。而数字则代表跳过几个字母。
举个例子：
如果我们给定单词 "word" 和缩写 "w1d"，我们会发现 "w1d" 是有效的缩写，因为它从原始单词 "word" 中去掉了 "o" 和 "r"，剩下了 "w" 和 "d"。
不过要注意，这个问题的核心在于要保证缩写中的字母顺序和原单词的字母顺序相一致。并且，我们还要考虑数字表示的跳过字符的数量。
例子：
-
"internationalization" -> "i18n" 这是一个典型的缩写，它表示的是从单词中去掉了很多个字符，只保留了首字母和最后一个字母，并且数字部分“18”表示跳过了18个字符。
-
"apple" -> "a2e" 这里的缩写是有效的，它表示从 "apple" 里去掉了 "p" 和 "p" 两个字母，只留下了 "a" 和 "e"。
-
"abc" -> "a1b" 这种缩写就是无效的，因为数字“1”代表跳过了一个字母，而剩下的字母 "b" 是按照原本顺序来的，跳过 "b" 后，应该剩下 "a" 和 "c" 才对。
算法思路
这个问题的核心在于如何判断缩写是否能通过跳过一些字符生成给定的单词。我们可以通过模拟的方式来解决这个问题，具体步骤如下：
-
遍历缩写字符串
：我们从缩写字符串的每个字符开始遍历，如果当前字符是字母，检查它是否匹配原始单词的当前位置。如果是数字，则表示跳过相应数量的字母。
-
匹配字母
：每次遇到字母时，检查它是否与原始单词的当前位置匹配。如果匹配，继续检查下一个字符。
-
跳过字母
：如果遇到数字，它表示跳过的字母个数。我们需要通过更新原始单词的指针来模拟跳过这些字母。
-
边界检查
：当遍历完缩写字符串时，我们还需要检查是否有剩余的字母在原始单词中没有被检查过。
Java实现
public class Abbreviation {
public boolean validWordAbbreviation(String word, String abbr) {
int i = 0; // word指针
int j = 0; // abbr指针
while (i if (Character.isDigit(abbr.charAt(j))) { // 如果当前字符是数字
if (abbr.charAt(j) == '0') return false; // 遇到0开头的数字无效
int skip = 0;
while (j skip = skip * 10 + (abbr.charAt(j) - '0'); // 计算跳过的字母个数
j++;
}
i += skip; // 跳过对应的字母
} else { // 如果是字母，直接进行匹配
if (word.charAt(i) != abbr.charAt(j)) return false; // 字母不匹配
i++;
j++;
}
}
// 最后检查两个字符串的指针是否都已经遍历完
return i == word.length() && j == abbr.length();
}
public static void main(String[] args) {
Abbreviation abbr = new Abbreviation();
System.out.println(abbr.validWordAbbreviation("internationalization", "i18n")); // true
System.out.println(abbr.validWordAbbreviation("apple", "a2e")); // true
System.out.println(abbr.validWordAbbreviation("abc", "a1b")); // false
System.out.println(abbr.validWordAbbreviation("submarine", "s1b1n")); // true
}
}
代码解析
-
检查数字的有效性
：我们首先判断当前字符是否是数字。如果是数字，我们会通过一个while循环来读取完整的数字（可能是多位数），并计算跳过的字符数。
-
匹配字母
：当我们遇到字母时，直接与单词中的字符进行匹配。如果匹配成功，则继续向后遍历。
-
终止条件
：当我们遍历完缩写字符串之后，仍然需要检查原单词是否也已被完全遍历。如果是，说明这个缩写是有效的。
性能分析
这个解法的时间复杂度是O(m + n)，其中m是单词的长度，n是缩写的长度。因为我们只遍历了单词和缩写两次，所以效率非常高。空间复杂度是O(1)，只用了几个额外的变量来存储索引和跳过的字符数量。
这道题虽然看起来简单，但实际考察了如何处理字母和数字的混合情况，以及如何通过指针模拟跳过字符的操作。
