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)

• "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):
"""

# 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:
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)