Coding

Valid Word Abbreviation

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their respective lengths. The lengths must not contain leading zeros.

For instance, a word like "celebration" could be abbreviated as (but is not limited to):

"c8n" ("c elebratio n")
"ce3r3on" ("ce leb r ati on")
"10" ("celebration")
"ce1e2r2o1" ("ce l e b r a t io n")
"celebration" (no substrings replaced)

The following are invalid abbreviations:

"c99n" ("c eleb r atio n", since the replaced substrings are adjacent)
"c012n" (contains leading zeros)
"c0elebration" (replaces an empty substring)

Given a string word and an abbreviation abbr, determine whether the string correctly matches the given abbreviation.

A substring is a contiguous, non-empty sequence of characters within a string.

Input: word = "development", abbr = "d9t" Output: true Explanation: The word "development" can be abbreviated as "d9t" ("d evelopmen t").

Input: word = "programming", abbr = "p8g" Output: true Explanation: The word "programming" can be abbreviated as "p8g" ("p rogrammin g").

Input: word = "keyboard", abbr = "k2y2d"

1 <= word.length <= 20
word consists of only lowercase English letters.
1 <= abbr.length <= 10
abbr consists of lowercase English letters and digits.
All integers in abbr will fit in a 32-bit integer.

cpp

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        // Your code goes here
    }
};

java

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        // Your code goes here
    }
}

python

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        # Your code goes here

javascript

class Solution {
    validWordAbbreviation(word, abbr) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public bool ValidWordAbbreviation(string word, string abbr)
    {
        // Your code goes here
    }
}

func validWordAbbreviation(word string, abbr string) bool {
    //your code goes here
}

Stuck? Show a way to structure it+

01Walk word and abbreviation with separate indices.
02Match letters directly.
03Parse consecutive digits into one positive skip count.
04Reject leading zeros, overruns, and mismatched endings.

Reference answer

Scan word and abbr together. A letter in the abbreviation must equal the current word character. On a digit, reject 0 as the first digit, parse the full number, and advance the word index by that count. At the end both indices must be exhausted exactly. Parsing is O(|word| + |abbr|) time and O(1) space. A count may span multiple digits, and a valid count may not skip past the end of the word. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you return the first mismatch location?
Tests: diagnostics
How would Unicode code points affect indexing?
Tests: representation

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question