leetcode
leetcode 351 ~ 400
有效单词缩写

有效单词缩写

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.6 MB


/*
 * 题目:有效单词缩写
 * 题目思路:
 * 使用Java Stream处理有效单词缩写问题。
 * 虽然Stream不是最适合处理此类问题的方法,但为了展示Stream的使用,这里尽量用Stream的方式处理。
 *
 * 方法:
 * 1. 将缩写中的字符和数字分开处理。
 * 2. 累积数字以跳过相应数量的字符。
 * 3. 检查字母是否匹配。
 */
 
import java.util.stream.IntStream;
 
public class ValidWordAbbreviationStream {
    public boolean validWordAbbreviation(String word, String abbr) {
        int[] indices = new int[]{0};
        return IntStream.range(0, abbr.length()).allMatch(j -> {
            if (Character.isDigit(abbr.charAt(j))) {
                if (abbr.charAt(j) == '0') return false;
                int start = j;
                while (j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
                    j++;
                }
                int num = Integer.parseInt(abbr.substring(start, j));
                indices[0] += num;
                return indices[0] <= word.length();
            } else {
                if (indices[0] >= word.length() || word.charAt(indices[0]) != abbr.charAt(j)) return false;
                indices[0]++;
                return true;
            }
        }) && indices[0] == word.length();
    }
}
 

解释

方法:

这个题解使用双指针 i 和 j 分别指向原单词 word 和缩写 abbr,同时用变量 num 记录缩写中的数字。遍历 abbr,如果遇到数字,则更新 num;如果遇到字母,则将 i 向后移动 num 个位置,num 重置为0,并比较 word[i] 和 abbr[j] 是否相等。最后判断 i+num 是否等于 word 的长度并且 j 是否等于 abbr 的长度,若相等则说明缩写与原单词匹配。

时间复杂度:

O(n+m)

空间复杂度:

O(1)

代码细节讲解

🦆
在题解中,你是如何处理数字的连续读取,以及如何防止处理中出现前导零的情况?
在题解中,数字的连续读取是通过一个循环实现的,每当遇到数字字符时,会将其转换为整数并累加到当前的数字变量 `num` 中,具体方法是将 `num` 乘以 10 然后加上新的数字,这样可以正确地从字符形式的数字构建整数。为了防止处理中出现前导零的情况,我们检查如果数字的第一个字符是 '0' 且 `num` 为 0(即这是一个新的数字开始),则直接返回 `False`,因为这种情况表示数字有不合法的前导零。
🦆
请问为什么在遇到字母时,需要先将i指针移动num个位置,而不是直接比较word[i]和abbr[j]?
这种处理方式是因为缩写 abbr 中的数字表示原单词 word 中相应位置跳过的字符数。因此,当遇到字母时,我们需要根据之前累积的数字 `num`(表示跳过的字符数量),首先将 `i` 指针向前移动 `num` 个位置,以对齐到正确的比较位置。然后,`num` 被重置为 0,以便处理后续的数字。如果直接比较而不移动 `i`,则会导致比较的位置不正确,因而无法正确验证缩写和原单词是否匹配。
🦆
在算法的末尾,为什么需要检查`i + num == len(word) and j == len(abbr)`,这一步骤是解决什么问题?
此检查确保所有字符和跳过的位置都已经完全匹配处理完毕。`i + num == len(word)` 确保 `i` 指针加上最后一个数字(如果有)正好可以走到 word 的末尾,即所有字符都被正确考虑且无多余字符。`j == len(abbr)` 确保 `j` 指针走到了 abbr 的末尾,即缩写中的每个字符和数字都被处理。只有这两个条件同时满足时,才能确认缩写完全符合原单词。
🦆
假设abbr中的数字表示跳过的字符数超过了word的长度,你的解决方案会如何处理这种情况?
在解决方案中,如果 `abbr` 中的数字表示的跳过字符数超过了 `word` 的长度,那么在处理过程中,`i` 指针会超出 `word` 的长度范围。这将在比较 `word[i]` 和 `abbr[j]` 或在最终的检查 `i + num == len(word)` 时被捕获。如果 `i` 指针在任何时候超出 `word` 的长度,算法会返回 `False`,表示缩写不匹配原单词。

相关问题

最短独占单词缩写

最短独占单词缩写

单词缩写

单词缩写