How hard is LeetCode 408. Valid Word Abbreviation?

LeetCode 408. Valid Word Abbreviation is rated Easy on LeetCode.

What is the time complexity of LeetCode 408. Valid Word Abbreviation?

The Python solution on this page runs in O(m + n), where m and n are the lengths of the string word and the string abbr respectively.

What is the space complexity of LeetCode 408. Valid Word Abbreviation?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 408. Valid Word Abbreviation cover?

LeetCode 408. Valid Word Abbreviation is tagged Two Pointers and String on LeetCode.

Is LeetCode 408. Valid Word Abbreviation a premium problem?

Yes. LeetCode 408. Valid Word Abbreviation is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Valid Word Abbreviation — LeetCode 408 Python Solution

EasyLeetCode PremiumTwo PointersString

Problem: #408
Pattern: Two Pointers
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Python solution

Python

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        m, n = len(word), len(abbr)
        i = j = x = 0
        while i < m and j < n:
            if abbr[j].isdigit():
                if abbr[j] == "0" and x == 0:
                    return False
                x = x * 10 + int(abbr[j])
            else:
                i += x
                x = 0
                if i >= m or word[i] != abbr[j]:
                    return False
                i += 1
            j += 1
        return i + x == m and j == n

Complexity

Measure	Complexity
Time	O(m + n), where m and n are the lengths of the string word and the string abbr respectively
Space	O(1) auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 408. Valid Word Abbreviation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 408. Valid Word Abbreviation?: LeetCode 408. Valid Word Abbreviation is rated Easy on LeetCode.
What is the time complexity of LeetCode 408. Valid Word Abbreviation?: The Python solution on this page runs in O(m + n), where m and n are the lengths of the string word and the string abbr respectively.
What is the space complexity of LeetCode 408. Valid Word Abbreviation?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 408. Valid Word Abbreviation cover?: LeetCode 408. Valid Word Abbreviation is tagged Two Pointers and String on LeetCode.
Is LeetCode 408. Valid Word Abbreviation a premium problem?: Yes. LeetCode 408. Valid Word Abbreviation is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.