408.Vaild_Word_Abbreviation(Easy).md

408. Valid Word Abbreviation (Easy)

Date and Time: Nov 21, 2024, 11:10 (EST)

Link: https://leetcode.com/problems/valid-word-abbreviation?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

Question:

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

• "s10n" ("s ubstitutio n")

• "sub4u4" ("sub stit u tion")

• "12" ("substitution")

• "su3i1u2on" ("su bst i t u ti on")

• "substitution" (no substrings replaced)

The following are not valid abbreviations:

• "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)

• "s010n" (has leading zeros)

• "s0ubstitution" (replaces an empty substring)

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

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

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

Output: true

Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Example 2:

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

Output: false

Explanation: The word "apple" cannot be abbreviated as "a2e".

Edge Case:

Input: word = "internationalization", abbr = "i5a11o1"

Output: true

Constraints:

• 1 <= word.length <= 20

• word consists of only lowercase English letters.

• 1 <= abbr.length <= 10

• abbr consists of lowercase English letters and digits.

• All the integers in abbr will fit in a 32-bit integer.

Walk-through:

1. Use two pointers i, j for word, abbr to compare if two chars are the same. We first check if abbr[j] == 0 or i >= len(word), we should return False, since no leading 0 is allowed and we check i inbound.

2. Then we detect if abbr[j].isdigit() and use while loop to extract number from abbr, and we update i += number.

3. We check if tmp == "" or not, if tmp != "", we can check if two chars word[i] == abbr[j], if not, we return False. Otherwise, we should update i += 1, j += 1. We can't just increment both pointers at anytime, because after we extracted number from abbr, we already incremented j += 1 to a non-digit char, and we also update i += number, and i is at a new char.

4. Lastly, return i == len(word) so we know we finish traversing word.

Python Solution:

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        # Use two ptrs i, j for word and abbr
        # If we dectect abbr[j] is digit, we use while loop to save the digit, then we update i with this number
        # Then, compare if current two chars are the same and update both ptrs
        # Lastly, make sure i == len(word), so we know we finish the whole word

        # TC: O(n), n = len(word), SC: O(1)
        i, j = 0, 0
        digits = "123456789"
        while j < len(abbr):
            # Check no leading 0, and i is inbound
            if abbr[j] == '0' or i >= len(word):
                return False
            # Extract digits from abbr
            tmp = ""
            while j < len(abbr) and abbr[j].isdigit():
                tmp += abbr[j]
                j += 1
            # Update i ptr when tmp is not empty
            if tmp:
                i += int(tmp)
            else:
                # Check if two chars are the same
                if word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
        return i == len(word)

Time Complexity: $O(n)$
Space Complexity: $O(1)$