LeetCode: 408 Valid Word Abbreviation

Given a non-empty string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A string abbr is a valid abbreviation of word if:

It can contain numbers representing how many characters to skip.
The numbers should not contain leading zeros.

Example:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

Explanation:

"i12iz4n" is a valid abbreviation of "internationalization".

Example:

Input: word = "apple", abbr = "a2e"
Output: false

Explanation:

"a2e" is not a valid abbreviation of "apple".

问题

给定一个非空字符串 word 和一个缩写 abbr，返回该字符串是否与给定的缩写匹配。

一个缩写 abbr 是 word 的有效缩写，如果：

它可以包含数字，表示要跳过的字符数。
数字不应包含前导零。

解决方案

双指针法

Approach: Two Pointers / 双指针法

This approach uses two pointers: one for the original word and another for the abbr. We iterate through both, comparing characters when necessary and using the numbers in the abbr to skip over characters in word. The two pointers ensure we accurately match the abbreviation to the word without missing or mismatching characters.

这种方法使用两个指针：一个用于原始 word，另一个用于 abbr。我们遍历两个字符串，在必要时比较字符，并使用 abbr 中的数字跳过 word 中的字符。这两个指针确保我们准确地将缩写与单词匹配，而不会遗漏或错配字符。

Implementation / 实现

Python

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        word_ptr, abbr_ptr = 0, 0
        while word_ptr < len(word) and abbr_ptr < len(abbr):
            if abbr[abbr_ptr].isdigit():
                if abbr[abbr_ptr] == '0':
                    return False  # Leading zeros are not allowed
                skip = 0
                while abbr_ptr < len(abbr) and abbr[abbr_ptr].isdigit():
                    skip = skip * 10 + int(abbr[abbr_ptr])
                    abbr_ptr += 1
                word_ptr += skip
            else:
                if word_ptr >= len(word) or word[word_ptr] != abbr[abbr_ptr]:
                    return False
                word_ptr += 1
                abbr_ptr += 1

        return word_ptr == len(word) and abbr_ptr == len(abbr)

Explanation / 解释

Initialize Two Pointers / 初始化两个指针
```
word_ptr, abbr_ptr = 0, 0
```
- English: We initialize two pointers word_ptr for the word and abbr_ptr for the abbr.
- Chinese: 我们初始化两个指针，word_ptr 用于 word，abbr_ptr 用于 abbr。
Iterate Through abbr and Match with word / 遍历 abbr 并与 word 匹配
```
while word_ptr < len(word) and abbr_ptr < len(abbr):
```
- English: We iterate through both word and abbr while both pointers are within bounds.
- Chinese: 我们遍历 word 和 abbr，同时确保两个指针都在界限内。
Handle Numbers in abbr / 处理 abbr 中的数字
```
if abbr[abbr_ptr].isdigit():
   if abbr[abbr_ptr] == '0':
       return False  # Leading zeros are not allowed
   skip = 0
   while abbr_ptr < len(abbr) and abbr[abbr_ptr].isdigit():
       skip = skip * 10 + int(abbr[abbr_ptr])
       abbr_ptr += 1
   word_ptr += skip
```
- English: If we encounter a number in abbr, we check for leading zeros (which are invalid) and then accumulate the full number using a loop to represent how many characters in word should be skipped.
- Chinese: 如果在 abbr 中遇到数字，我们首先检查是否有前导零（这是无效的），然后使用循环累加完整的数字，表示在 word 中要跳过多少个字符。
Handle Character Matching / 处理字符匹配
```
else:
   if word_ptr >= len(word) or word[word_ptr] != abbr[abbr_ptr]:
       return False
   word_ptr += 1
   abbr_ptr += 1
```
- English: If we encounter a character in abbr, we compare it with the corresponding character in word. If they don't match, we return False.
- Chinese: 如果在 abbr 中遇到字符，我们将其与 word 中对应的字符进行比较。如果它们不匹配，则返回 False。
Check If Both Strings Are Fully Processed / 检查两个字符串是否完全处理
```
return word_ptr == len(word) and abbr_ptr == len(abbr)
```
- English: After processing both word and abbr, both pointers should be at the end of their respective strings. If so, we return True.
- Chinese: 处理完 word 和 abbr 后，两个指针都应该到达各自字符串的末尾。如果是这样，我们返回 True。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the length of the abbr. We iterate through both the abbr and word, processing each character or digit once.
Space Complexity / 空间复杂度: O(1), since we only use a constant amount of extra space for the pointers and temporary variables.

Key Concept / 关键概念

Two Pointers / 双指针: The two-pointer technique allows us to compare word and abbr character by character, handling both letters and numbers efficiently.
双指针: 双指针技术允许我们逐个字符比较 word 和 abbr，高效地处理字母和数字。

Summary / 总结

English: The Two Pointers method efficiently matches the abbreviation to the word by handling characters and numbers separately. It ensures that both conditions—matching characters and skipping numbers—are correctly processed.
Chinese: 双指针方法通过分别处理字符和数字，能够高效地将缩写与单词匹配。它确保正确处理字符匹配和跳过数字的两个条件。

Tips / 提示

English: Practice using two pointers to efficiently handle problems that involve comparing two sequences or strings, especially when handling mixed input like characters and numbers.
Chinese: 练习使用双指针高效处理涉及比较两个序列或字符串的问题，特别是在处理字符和数字混合输入时。

Solution Template for Similar Questions / 提示

English: When comparing two sequences (such as strings or arrays), consider using two pointers to process both inputs simultaneously, especially if they contain different types of elements (e.g., characters and numbers).
Chinese: 在比较两个序列（如字符串或数组）时，考虑使用双指针来同时处理两个输入，特别是当它们包含不同类型的元素（例如字符和数字）时。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice using the two-pointer technique to handle problems involving mixed data types, as it can simplify and optimize comparison problems.
Chinese: 练习使用双指针技术来处理涉及混合数据类型的问题，因为它可以简化和优化比较问题。

VALID WORD ABBREVIATION | LEETCODE # 408 | PYTHON TWO POINTERS SOLUTION by Cracking FAANG

Post Views: 25

CODEBITWAVE