LeetCode刷题实战408：有效单词缩写
LeetCode刷题实战408：有效单词缩写
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 有效单词缩写，我们先来看题面：
https://leetcode-cn.com/problems/valid-word-abbreviation/
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
给一个 非空 字符串 s 和一个单词缩写 abbr ，判断这个缩写是否可以是给定单词的缩写。
字符串 "word" 的所有有效缩写为：
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
注意单词 "word" 的所有有效缩写仅包含以上这些。任何其他的字符串都不是 "word" 的有效缩写。
注意:
假设字符串 s 仅包含小写字母且 abbr 只包含小写字母和数字。
示例
示例 1:
给定 s = "internationalization", abbr = "i12iz4n":
函数返回 true.
示例 2:
给定 s = "apple", abbr = "a2e":
函数返回 false.解题
https://blog.csdn.net/qq_29051413/article/details/108846427
通过示例可知，所谓的缩写就是对某些子串用子串的长度来代替。
遍历 abbr 的每一个字符：
1、当出现带有前导 0 的数字，则直接 false，例如：friend 缩写成 f04d 就是不符合题意的；
2、abbr 对应位置的字符要和 word 一致，例如：word 的缩写 w2d，其中 d 是第 3 位的字符，两者的第 3 位的字符应该都是 d，否则 false；
3、缩写展开后的长度应该和原单词一致，例如，word 长度为 4，缩写 1or1 展开后长度也是 4，否则 false。
class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
char[] chars = abbr.toCharArray();
int num = 0; // 缩写中的数字，不能出现前导0
int next = 0; // 遍历 chars 的指针
for (char c : chars) {
// 如果是数字，则拼接成最后的样子
if (c >= '0' && c <= '9') {
// 前导0数字不合法
if (num == 0 && c == '0') return false;
num = num * 10 + (c - '0');
continue;
}
next = next + num; // 更新指针
// 如果 next 超出了 word 的长度，说明不是 word 的缩写
// 或者，如果 word 和 abbr 在 next 位置的字符不一致，则说明不是 word 的缩写
if (next >= word.length() || (word.charAt(next) != c)) {
return false;
}
next++;
num = 0;
}
return next + num == word.length();
}
}好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
腾讯云开发者
