Valid Word Abbreviation

Easy
632.

Valid Word Abbreviation

Valid Word Abbreviation is an easy coding problem on strings and two pointers, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {string} abbr
 * @return {boolean}
 */
var validWordAbbreviation = function(word, abbr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Word Abbreviation — Solution in Python, Java & C++

Valid Word Abbreviation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Valid Word Abbreviation is an easy coding problem on strings and two pointers, asked in Amazon, Google and Meta interviews.

  • Difficulty: Easy
  • Topics: Strings, Two Pointers
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Valid Word Abbreviation

  1. Hint 1

    Two pointers, one walking word and one walking abbr.

  2. Hint 2

    A digit run in abbr is a jump for the word pointer, so parse the whole number before jumping.

  3. Hint 3

    Both pointers must finish exactly at the end — a match that runs out early is not a match.

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)

Java

public static boolean validWordAbbreviation(String word, String abbr) {
    int i = 0, j = 0;
    while (i < word.length() && j < abbr.length()) {
        char c = abbr.charAt(j);
        if (c >= '0' && c <= '9') {
            if (c == '0') return false;
            int num = 0;
            while (j < abbr.length() && abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
                num = num * 10 + (abbr.charAt(j) - '0');
                j++;
            }
            i += num;
        } else {
            if (word.charAt(i) != c) return false;
            i++;
            j++;
        }
    }
    return i == word.length() && j == abbr.length();
}

C++

bool validWordAbbreviation(string word, string abbr) {
    int i = 0, j = 0;
    int n = (int) word.size(), m = (int) abbr.size();
    while (i < n && j < m) {
        char c = abbr[j];
        if (c >= '0' && c <= '9') {
            if (c == '0') return false;
            int num = 0;
            while (j < m && abbr[j] >= '0' && abbr[j] <= '9') {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            i += num;
        } else {
            if (word[i] != c) return false;
            i++;
            j++;
        }
    }
    return i == n && j == m;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique