Valid Word Abbreviation — Easy Problem & Solution

Problem statement

An abbreviation replaces any number of non-adjacent, non-empty substrings of a word with their lengths. For example "codekairo" can be abbreviated as "c7o" or "co5ro", but not "c1de5" — 1 and the following letters would come from adjacent replacements written separately.

A number in the abbreviation must not have a leading zero.

Given word and abbr, return true if abbr is a valid abbreviation of word.

Example 1

Input: word = "codekairo", abbr = "c7o"
Output: true
Explanation: c, then 7 letters skipped, then o.

Example 2

Input: word = "codekairo", abbr = "c07o"
Output: false
Explanation: A leading zero is never allowed.

Example 3

Input: word = "apple", abbr = "a2e"
Output: false
Explanation: a2e covers only 4 characters; apple has 5.

Constraints

• 1 <= word.length <= 20
• 1 <= abbr.length <= 10
• word consists of lowercase letters.
• abbr consists of lowercase letters and digits.

How to solve Valid Word Abbreviation

Walk both strings with independent pointers. A letter in abbr must match the current letter of word; a digit run is an instruction to skip that many characters of word.

Approach

1. While both pointers are in range: if abbr[j] is a digit, reject a leading '0', then parse the full number and advance i by it.
2. Otherwise compare word[i] with abbr[j] and advance both on a match, rejecting on a mismatch.
3. Return true only when both pointers have reached the end.

Why it works

Parsing the entire digit run at once is what enforces the 'non-adjacent' rule: two adjacent replacements would have to be written as one number, so any well-formed abbreviation has letters between its numbers. Requiring both pointers to land exactly at the end rejects abbreviations that cover too little or skip past the end.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Skipping the leading-zero check accepts "c07o".
• Returning true when only i has reached the end leaves unconsumed abbreviation characters.
• i can overshoot word.length after a jump — the final equality check must be exact, not >=.

Reference solution

Python

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

JavaScript

var validWordAbbreviation = function(word, abbr) {
    var i = 0, j = 0;
    while (i < word.length && j < abbr.length) {
        var c = abbr.charAt(j);
        if (c >= "0" && c <= "9") {
            if (c === "0") return false;
            var num = 0;
            while (j < abbr.length && abbr.charAt(j) >= "0" && abbr.charAt(j) <= "9") {
                num = num * 10 + (abbr.charCodeAt(j) - 48);
                j++;
            }
            i += num;
        } else {
            if (word.charAt(i) !== c) return false;
            i++;
            j++;
        }
    }
    return i === word.length && j === abbr.length;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Original Typed String I Easy
• Rearrange Characters to Make Target String Easy
• Number of Strings That Appear as Substrings in Word Easy
• Circular Sentence Easy
• Number of Senior Citizens Easy
• Find Words Containing Character Easy