有效单词缩写
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在题解中,你是如何处理数字的连续读取,以及如何防止处理中出现前导零的情况?
▷🦆
请问为什么在遇到字母时,需要先将i指针移动num个位置,而不是直接比较word[i]和abbr[j]?
▷🦆
在算法的末尾,为什么需要检查`i + num == len(word) and j == len(abbr)`,这一步骤是解决什么问题?
▷🦆
假设abbr中的数字表示跳过的字符数超过了word的长度,你的解决方案会如何处理这种情况?
▷