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();
    }
}