Valid Word Abbreviation

Problem#

Given a string word and an abbreviation abbr (letters interleaved with non-negative integer “skip counts”), return true if the abbreviation correctly describes the word. Leading zeros in any number are invalid ("01" is not a legal skip).

Examples#

word = "internationalization", abbr = "i12iz4n" → true (i + skip 12 + iz + skip 4 + n)
word = "apple", abbr = "a2e" → false (skip of 2 lands on l, not e)
word = "a", abbr = "01" → false (leading zero)

Constraints#

1 <= word.length <= 20, lowercase letters.
1 <= abbr.length <= 10, lowercase letters and digits.

Hints#

Hint 1

Walk both strings with two indices; when you hit a digit, consume the whole number before jumping.

Hint 2

Reject any number that starts with '0' immediately — no need to parse further.

Approach#

Regex / split — readable but pays allocation cost and hides the leading-zero edge case.

Two pointers — i over word, j over abbr. When abbr[j] is a digit, accumulate the number and advance i by it. Linear, no allocations.

Solution#

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        const int n = word.size(), m = abbr.size();
        while (i < n && j < m) {
            if (isdigit(abbr[j])) {
                if (abbr[j] == '0') return false;     // leading zero
                int num = 0;
                while (j < m && isdigit(abbr[j])) {
                    num = num * 10 + (abbr[j] - '0');
                    ++j;
                }
                i += num;
            } else {
                if (word[i] != abbr[j]) return false;
                ++i; ++j;
            }
        }
        return i == n && j == m;
    }
};

func validWordAbbreviation(word string, abbr string) bool {
    isDigit := func(c byte) bool { return c >= '0' && c <= '9' }
    i, j := 0, 0
    n, m := len(word), len(abbr)
    for i < n && j < m {
        if isDigit(abbr[j]) {
            if abbr[j] == '0' {
                return false // leading zero
            }
            num := 0
            for j < m && isDigit(abbr[j]) {
                num = num*10 + int(abbr[j]-'0')
                j++
            }
            i += num
        } else {
            if word[i] != abbr[j] {
                return false
            }
            i++
            j++
        }
    }
    return i == n && j == m
}

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i, j = 0, 0
        n, m = len(word), len(abbr)
        while i < n and j < m:
            if abbr[j].isdigit():
                if abbr[j] == '0':
                    return False  # leading zero
                num = 0
                while j < m 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 == n and j == m

function validWordAbbreviation(word, abbr) {
    const isDigit = (c) => c >= '0' && c <= '9';
    let i = 0, j = 0;
    const n = word.length, m = abbr.length;
    while (i < n && j < m) {
        if (isDigit(abbr[j])) {
            if (abbr[j] === '0') return false; // leading zero
            let num = 0;
            while (j < m && isDigit(abbr[j])) {
                num = num * 10 + (abbr.charCodeAt(j) - 48);
                j++;
            }
            i += num;
        } else {
            if (word[i] !== abbr[j]) return false;
            i++;
            j++;
        }
    }
    return i === n && j === m;
}

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, j = 0;
        int n = word.length(), m = abbr.length();
        while (i < n && j < m) {
            char c = abbr.charAt(j);
            if (Character.isDigit(c)) {
                if (c == '0') return false; // leading zero
                int num = 0;
                while (j < m && Character.isDigit(abbr.charAt(j))) {
                    num = num * 10 + (abbr.charAt(j) - '0');
                    j++;
                }
                i += num;
            } else {
                if (word.charAt(i) != c) return false;
                i++;
                j++;
            }
        }
        return i == n && j == m;
    }
}

function validWordAbbreviation(word: string, abbr: string): boolean {
    const isDigit = (c: string): boolean => c >= '0' && c <= '9';
    let i = 0, j = 0;
    const n = word.length, m = abbr.length;
    while (i < n && j < m) {
        if (isDigit(abbr[j])) {
            if (abbr[j] === '0') return false; // leading zero
            let num = 0;
            while (j < m && isDigit(abbr[j])) {
                num = num * 10 + (abbr.charCodeAt(j) - 48);
                j++;
            }
            i += num;
        } else {
            if (word[i] !== abbr[j]) return false;
            i++;
            j++;
        }
    }
    return i === n && j === m;
}

Editorial#

The two pointers play different roles: j walks abbr token-by-token (either a single letter or an entire digit run), and i jumps over word by exactly the skip distance. Treating the digit run atomically is what makes the algorithm linear — we never re-scan characters. The leading-zero check is a one-liner because a legal number ≥ 1 cannot start with '0', and '0' itself is illegal too (skipping zero characters is meaningless and explicitly disallowed). The final equality check (i == n && j == m) catches the case where one string is exhausted before the other.

Complexity#

Time: O(n + m) — single pass over each string.
Space: O(1) — just the two indices and the running number.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#