LeetCode第408题：有效单词缩写

难度：简单

题目链接：LeetCode第408题

题目描述

给一个 非空 字符串 s 和一个缩写 abbr ，请根据这个缩写的规则判断它是否可以是这个字符串的缩写。

字符串的缩写规则如下：

1. 字符串中的每个字母都可以用它的出现次数来替代
2. 缩写必须以字母开头和结尾

示例 1：

输入: s = "internationalization", abbr = "i12iz4n"
输出: true
解释: "internationalization" 可以缩写为 "i12iz4n"。

示例 2：

输入: s = "apple", abbr = "a2e"
输出: false
解释: "apple" 不能缩写为 "a2e"。

提示：

• 1 <= s.length <= 20
• s 仅由小写英文字母组成
• 1 <= abbr.length <= 10
• abbr 由小写英文字母和数字组成
• abbr 中的所有数字均符合 32-bit 整数范围

解题思路

这道题目的核心思路是：

1. 使用双指针分别遍历原字符串和缩写字符串
2. 遇到字母时直接比较
3. 遇到数字时需要处理连续的数字，并在原字符串中跳过相应数量的字符
4. 最后检查两个指针是否都到达了字符串末尾

算法流程

1. 初始化两个指针 i 和 j，分别指向原字符串 s 和缩写字符串 abbr 的开头
2. 当 j 未到达 abbr 末尾时：
   • 如果当前字符是数字：
     • 如果数字是0，直接返回false（因为不允许前导零）
     • 累加连续的数字，得到需要跳过的字符数
     • 在原字符串中跳过相应数量的字符
   • 如果当前字符是字母：
     • 比较两个字符串中的字符是否相同
3. 最后检查两个指针是否都到达了字符串末尾

代码实现

C# 实现

public class Solution {
    public bool ValidWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        
        while (i < word.Length && j < abbr.Length) {
            // 如果是字母，直接比较
            if (char.IsLetter(abbr[j])) {
                if (i >= word.Length || word[i] != abbr[j]) {
                    return false;
                }
                i++;
                j++;
                continue;
            }
            
            // 处理数字
            if (abbr[j] == '0') {  // 不允许前导零
                return false;
            }
            
            // 计算数字值
            int num = 0;
            while (j < abbr.Length && char.IsDigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            
            i += num;  // 跳过相应数量的字符
            if (i > word.Length) {  // 检查是否越界
                return false;
            }
        }
        
        // 检查是否都到达末尾
        return i == word.Length && j == abbr.Length;
    }
}

Python 实现

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i = j = 0
        
        while i < len(word) and j < len(abbr):
            # 如果是字母，直接比较
            if abbr[j].isalpha():
                if i >= len(word) or word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
                continue
            
            # 处理数字
            if abbr[j] == '0':  # 不允许前导零
                return False
            
            # 计算数字值
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            
            i += num  # 跳过相应数量的字符
            if i > len(word):  # 检查是否越界
                return False
        
        # 检查是否都到达末尾
        return i == len(word) and j == len(abbr)

C++ 实现

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        
        while (i < word.length() && j < abbr.length()) {
            // 如果是字母，直接比较
            if (isalpha(abbr[j])) {
                if (i >= word.length() || word[i] != abbr[j]) {
                    return false;
                }
                i++;
                j++;
                continue;
            }
            
            // 处理数字
            if (abbr[j] == '0') {  // 不允许前导零
                return false;
            }
            
            // 计算数字值
            int num = 0;
            while (j < abbr.length() && isdigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            
            i += num;  // 跳过相应数量的字符
            if (i > word.length()) {  // 检查是否越界
                return false;
            }
        }
        
        // 检查是否都到达末尾
        return i == word.length() && j == abbr.length();
    }
};

执行结果

C# 实现

• 执行用时：72 ms
• 内存消耗：36.8 MB

Python 实现

• 执行用时：32 ms
• 内存消耗：15.1 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：6.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	72 ms	36.8 MB	代码结构清晰，但性能较差
Python	32 ms	15.1 MB	代码简洁，性能中等
C++	0 ms	6.2 MB	性能最优，内存占用最小

代码亮点

1. 🎯 使用双指针技术高效处理字符串比较
2. 💡 巧妙处理数字部分，支持多位数字的情况
3. 🔍 细致的边界条件处理，包括前导零检查
4. 🎨 代码结构清晰，逻辑分支处理得当

常见错误分析

1. 🚫 忽略前导零的特殊处理
2. 🚫 未正确处理多位数字的情况
3. 🚫 越界检查不完整
4. 🚫 未检查最终两个指针是否同时到达末尾

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
双指针法	O(n)	O(1)	实现简单，空间效率高	需要仔细处理边界条件
正则表达式	O(n)	O(n)	代码简洁	性能较差，不易理解

相关题目

• LeetCode 65. 有效数字 - 困难
• LeetCode 388. 文件的最长绝对路径 - 中等

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第408题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！