Problem Statement

Description

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.

Examples

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".

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.

Key Insights

This is a two pointer problem. The trick is to carefully move the a pointer through the abbr string and the w pointer through the word string. As we move these pointers through their respective strings, we need to keep an eye out for leading zeros. When we come across a valid substitution in abbr, we move the w pointer ahead by the the number of characters abbreviated. If both pointers make it to the end of their respective strings without triggering a return False, we know that the abbreviation abbr is valid.

Note: A sequence of digits in a string can be converted into a number very easily moving from from left to right and multiplying the current value by 10 for example:

"456"

num =    0
num = 10*0 + 4  = 4
num = 10*4 + 5  = 45
num = 10*45 + 6 = 456

Python Solution

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        """
            Edge cases(s):
                [x] Cannot have leading zeroes
        """

        # Initialize two pointers to 0
        a = w = 0

        # Loop through both strings
        while a < len(abbr) and w < len(word):
            
            if abbr[a].isalpha():
                # If letters match up, increment both pointers
                if abbr[a] == word[w]:
                    a += 1
                    w += 1
                # If letter's don't match up, return False
                else:
                    return False
            else:
                # Check for leading zeros
                if abbr[a] == "0":
                    return False

                # Determine the number of characters that have been abbreviated
                temp = 0
                while a < len(abbr) and abbr[a].isdigit():
                    temp = 10*temp + int(abbr[a])
                    a += 1
                # temp will be greater than or equal to 1
                w += temp
        
        # If the "a" and "w" pointers end up at the same place at the end,
        # we know that abbr is valid.
        return a == len(abbr) and w == len(word)