Problem description:

A string can be abbreviated by replacing any number of non-adjacent substrings with their lengths. 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)

Note that "s55n" ("s ubsti tutio n") is not a valid abbreviation of "substitution" because the replaced substrings are adjacent.

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= word.length <= 20
  • word consists of only lowercase English letters.
  • 1 <= abrr.length <= 10
  • abbr consists of lowercase English letters and digits.
  • All the integers in abrr will fit in a 32-bit integer.

Solution:

  1. two pointer for both strings
  2. If encounter number in abbr
    1. start with 0: return False
    2. it’s a valid number: get number add to i
  3. check if characters on word[i] and abbr[j] are the same
  4. since the number in abbr might directly add i to the end of word, need to check if i and j both reached to the end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i, j = 0, 0
        while i < len(word) and j < len(abbr):
            if abbr[j].isdigit():
                # get the number, add number to i
                if abbr[j] == '0': return False
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num*10 + ord(abbr[j])-ord('0')
                    j += 1
                if num == 0:
                    return False
                i += num
            else:
                if word[i] != abbr[j]: return False
                i, j = i+1, j+1
        return i == len(word) and j == len(abbr)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: