408. Valid Word Abbreviation

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

Solution Approach

To determine if the abbreviation is valid, the algorithm iterates through the abbreviation while adjusting the index of the original word based on the digits, ensuring that characters and their positions match accordingly without skipping or misplacing characters.

Algorithm

1. Parse the Abbreviation: Iterate through each character of the abbreviation. If it’s a digit, build the full number to determine how many characters to skip in the original word.2
2. Match Characters: As you parse digits, skip the corresponding number of characters in the original word. When encountering a letter, check if it matches the current character in the original word.
3. Verify End Conditions: Ensure that after processing all characters in the abbreviation, any remaining characters in the original word correspond to the last parsed number or are empty, confirming that the abbreviation fully matches the original word.

   Complexity

   time complexity: O(n + m) space complexity: O(1)

Implement

    class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        digit, idx = 0, 0
        for i in range(len(abbr)):
            if abbr[i] == '0' and digit == 0:
                return False
            if abbr[i].isdigit():
                digit = digit * 10 + int(abbr[i])
            else:
                idx += digit
                digit = 0
                if idx >= len(word) or word[idx] != abbr[i]:
                    return False
                idx += 1
        return len(word) - idx == digit

   

    
    

Twitter  facebook  Email