408、有效单词缩写

leetcode 双指针字符串

Created At : 2024-06-27 22:06

Count:542 Views 👀 :

Comment:

题目
1. 示例 1：
2. 示例 2：
分析
1. 遍历，下标同步

题目

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

分析

分别遍历，字符串同步下标。

遍历，下标同步

算法描述：

初始化数字记录变量 digit
初始化下标遍历对象 idx
遍历缩写字符串
- 获取第i个字符
- 数字以0开始，算法结束，不是有效的缩写字符串
- 字符是数字，则：
  - 更新数字 digit = digit * 10 + (c - '0')
- 否则：
  - 更新 idx: idx = idx + digit
  - 重置 digit: digit = 0
  - 字符串长度、字符匹配判断，不符合则不是有效缩写字符串
  - idx累加
判断最后的idx是否是字符串的最后的位置。

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int digit = 0;
        int idx = 0;
        for (int i = 0; i < abbr.length(); i++) {
            char c = abbr.charAt(i);
            if (c == '0' && digit == 0) {
                return false;
            }
            if (Character.isDigit(c)) {
                digit = digit * 10 + (c - '0');
            } else {
                idx += digit;
                digit = 0;
                if (idx >= word.length() || word.charAt(idx) != c) {
                    return false;
                }
                idx++;
            }
        }
        return word.length() - idx == digit;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com