Thomas Ngo

Software Engineer

1 minute read

Problem Statement

problem

Intuition

The problem is asking us to verify if an abbreviation matches the full word. The abbreviation may contain numbers, which represent a number of characters to skip in the original word. Our first intuition is to iterate through the abbreviation, interpreting digits as skips and ensuring that non-digit characters match the corresponding characters in the word.

Approach

We maintain two pointers, one for traversing the abbreviation and another for tracking our position in the word. As we go through the abbreviation:

  • If we encounter a number, we convert it into an integer and skip that many characters in the word.
  • If we encounter a letter, we check if it matches the letter in the corresponding position of the word.
  • If at any point the number of characters to skip goes beyond the word length or if a character mismatch occurs, we return False.
  • Finally, we ensure both the abbreviation and word are fully traversed simultaneously for a valid match.

Complexity

  • Time complexity:
    The time complexity of this approach is \(O(n + m)\), where \(n\) is the length of the word and \(m\) is the length of the abbreviation. In the worst case, we scan through both the word and the abbreviation.

  • Space complexity:
    The space complexity is \(O(1)\) because we are only using a few extra variables, and no additional space that scales with input size.

Code

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        if len(word) < len(abbr):
            return False
        word_ptr = 0
        len_abbr = len(abbr)
        i = 0
        while i < len(abbr):
            if abbr[i].isdigit():
                number_str = []
                while i < len(abbr) and abbr[i].isdigit():
                    number_str.append(abbr[i])
                    if number_str[0] == '0':
                        return False
                    i += 1
                curr_len = int(''.join(number_str))
                word_ptr += curr_len
            else:
                if word[word_ptr] != abbr[i]:
                    return False
                word_ptr += 1
                i += 1
            if word_ptr >= len(word):
                break
        return word_ptr == len(word) and i == len(abbr)

Discussion Solution

class Solution:
    def validWordAbbreviation(self, word, abbr):
        i = j = 0
        m, n = len(word), len(abbr)
        while i < m and j < n:
            if word[i] == abbr[j]:
                i += 1
                j += 1
            elif abbr[j] == "0":
                return False
            elif abbr[j].isnumeric():
                k = j
                while k < n and abbr[k].isnumeric():
                    k += 1
                i += int(abbr[j:k])
                j = k
            else:
                return False
        return i == m and j == n

You may also enjoy