Leetcode 408: Valid Word Abbreviation

Two pointers track two strings and check constraints/conditions

Problem description

The two-pointer approach in a nutshell

1. Initialize two pointers: i=0 for the word and j=0 for the abbreviation.
2. Loop while both pointers haven’t reached the end of their strings.

• If the current character in the abbreviation is numeric and not ‘0’, parse the entire number to get the count. Increase the word pointer i by this count.
• If the current character is non-numeric, compare it with the current character in the word. If they are not equal, return false.
• Increase both pointers.

3. At the end of the loop, check if both pointers have reached the ends of their strings. If they have, return true. Otherwise, return false.

Python solution

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        #  Initialize two pointers:
        #   i=0 for the word and j=0 for the abbreviation
        i, j = 0, 0

        while i < len(word) and j < len(abbr):
            if word[i] == abbr[j]:
                i += 1
                j += 1
                continue

            # When word[i] != abbr[j],
            #   but abbr[j] is not a digit,
            #   we immediately know that abbr is not a valid abbreviation
            if not abbr[j].isdigit():
                return False

            # Leading '0' immdiately shows abbr is not a valid abbreviation
            if abbr[j] == "0":
                return False

            # If the current character in the abbreviation is numeric and
            #   not '0', parse the entire number to get the count.
            #   Increase the word pointer i by this count.
            start = j
            while j < len(abbr) and abbr[j].isdigit():
                j += 1

            i += int(abbr[start:j])

        # At the end of the loop, check if both pointers
        #     have reached the ends of their strings.
        #     If they have, return true. Otherwise, return false
        return i == len(word) and j == len(abbr)

Space and time complexity

With n denoting the length of the word:

• Space complexity: O(1) — With the two pointer approach, we only use constant space to store the two pointers
• Time complexity: O(n) — The worst-case scenario where all characters in the abbreviation are letters and are identical to those in word, O(n) time is required for the iteration

Unit test examples (with pytest)

def test_valid_word_abbreviation():
    assert Solution().validWordAbbreviation("internationalization", "i12iz4n")
    assert not Solution().validWordAbbreviation("apple", "a2e")