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):
"s ubstitutio n")
"sub stit u tion")
"su bst i t u ti on")
"substitution"(no substrings replaced) The following are not valid abbreviations:
"s ubsti tutio n", the replaced substrings are adjacent)
"s010n"(has leading zeros)
"s0ubstitution"(replaces an empty substring) Given a string
wordand an abbreviation
abbr, return whether the string matches the given abbreviation.
A substring is a contiguous non-empty sequence of characters within a string.
word = "internationalization",
abbr = "i12iz4n"
Output: true Explanation:
The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").
word = "apple", abbr = "a2e"
The word "apple" cannot be abbreviated as "a2e".
1 <= word.length <= 20
wordconsists of only lowercase English letters.
1 <= abbr.length <= 10
abbrconsists of lowercase English letters and digits.
- All the integers in
abbrwill fit in a 32-bit integer.
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
"456" num = 0 num = 10*0 + 4 = 4 num = 10*4 + 5 = 45 num = 10*45 + 6 = 456
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)