Valid Word Abbreviation

Q: What is the best time complexity for Valid Word Abbreviation?

Optimal (two pointers) runs in O(n + m) time and O(1) extra space. Each character of `abbr` is read once; `i` only moves forward.

Q: Which pattern does Valid Word Abbreviation use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Q: Is there a brute force solution for Valid Word Abbreviation?

Yes. Brute force (expand, then compare) takes O(n + m) time and O(n) space. Turn the abbreviation into a full-length pattern: copy letters, and replace each number by that many wildcard characters.

Q: Which edge cases should I test for Valid Word Abbreviation?

A number with a leading zero, including a lone "0"; A number larger than the remaining letters of word; The whole word replaced by its length, like "9" for a 9-letter word; Letters left over in word or in abbr after the other runs out.

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atMeta LinkedIn

Valid Word Abbreviation is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers), runs in O(n + m) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (expand, then compare) up.

Problem

A word can be abbreviated by replacing any number of non-overlapping, non-adjacent runs of letters with the length of each run. For example, "keyboard" could become "k3oard", "8" or "key2ar1". Numbers in an abbreviation never have leading zeros, so "k03oard" is not allowed, and a run cannot have length zero.

Given a string word and a candidate abbreviation abbr, return true if abbr is a valid abbreviation of word, and false otherwise.

Examples

Example 1

Input: word = "microwave", abbr = "m2r4e"
Output: true
Why: m, skip "ic", r, skip "owav", e: every piece lines up and the lengths match.

Example 2

Input: word = "notebook", abbr = "n06k"
Output: false
Why: A number may not start with 0, so "06" is not a valid skip.

Example 3

Input: word = "apple", abbr = "a3"
Output: false
Why: "a" plus 3 skipped letters covers only 4 of the 5 letters.

Constraints

1 <= word.length <= 10^4, lowercase English letters only.
1 <= abbr.length <= 10^4, lowercase English letters and digits.
Every number written in abbr fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 19 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (expand, then compare)	`O(n + m)`	`O(n)`
Optimal (two pointers)	`O(n + m)`	`O(1)`

1Brute force (expand, then compare)

TimeO(n + m)Each character of `abbr` is read once and the pattern is at most n long, then compared once.

SpaceO(n)The expanded pattern can be as long as `word`.

Turn the abbreviation into a full-length pattern: copy letters, and replace each number by that many wildcard characters. Then compare the pattern with word position by position, where a wildcard matches anything.

Scan abbr; a letter is appended, a digit run is parsed (reject a leading '0') and that many '?' are appended.
Stop early with false if the pattern grows longer than word.
The pattern must have the same length as word and match it at every non-'?' position.

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int n = word.length();
        StringBuilder sb = new StringBuilder();
        int j = 0;
        while (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');
                    if (num > n) return false;
                    j++;
                }
                for (int k = 0; k < num; k++) sb.append('?');
            } else {
                sb.append(c);
                j++;
            }
            if (sb.length() > n) return false;
        }
        if (sb.length() != n) return false;
        for (int k = 0; k < n; k++) {
            if (sb.charAt(k) != '?' && sb.charAt(k) != word.charAt(k)) return false;
        }
        return true;
    }
}

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        n = len(word)
        pattern = []
        j = 0
        while j < len(abbr):
            c = abbr[j]
            if c.isdigit():
                if c == '0':
                    return False
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    if num > n:
                        return False
                    j += 1
                pattern.extend('?' * num)
            else:
                pattern.append(c)
                j += 1
            if len(pattern) > n:
                return False
        if len(pattern) != n:
            return False
        for k in range(n):
            if pattern[k] != '?' and pattern[k] != word[k]:
                return False
        return True

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int n = word.size(), m = abbr.size();
        string pattern;
        int j = 0;
        while (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');
                    if (num > n) return false;
                    j++;
                }
                pattern.append(num, '?');
            } else {
                pattern.push_back(c);
                j++;
            }
            if ((int)pattern.size() > n) return false;
        }
        if ((int)pattern.size() != n) return false;
        for (int k = 0; k < n; k++) {
            if (pattern[k] != '?' && pattern[k] != word[k]) return false;
        }
        return true;
    }
};

function validWordAbbreviation(word, abbr) {
    const n = word.length, m = abbr.length;
    const pattern = [];
    let j = 0;
    while (j < m) {
        const c = abbr[j];
        if (c >= '0' && c <= '9') {
            if (c === '0') return false;
            let num = 0;
            while (j < m && abbr[j] >= '0' && abbr[j] <= '9') {
                num = num * 10 + (abbr.charCodeAt(j) - 48);
                if (num > n) return false;
                j++;
            }
            for (let k = 0; k < num; k++) pattern.push('?');
        } else {
            pattern.push(c);
            j++;
        }
        if (pattern.length > n) return false;
    }
    if (pattern.length !== n) return false;
    for (let k = 0; k < n; k++) {
        if (pattern[k] !== '?' && pattern[k] !== word[k]) return false;
    }
    return true;
}

2Optimal (two pointers)

TimeO(n + m)Each character of `abbr` is read once; `i` only moves forward.

SpaceO(1)Two pointers and one number.

Skip the expansion. Keep pointer i in word and j in abbr. A letter must equal word[i] and advances both; a number (no leading zero) moves i forward by its value. Valid exactly when both pointers finish together.

While i < n and j < m: if abbr[j] is a digit, reject '0', parse the full number, and add it to i.
Otherwise require word[i] == abbr[j], then i++, j++.
Return i == n && j == m.

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

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

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int n = word.size(), m = abbr.size();
        int i = 0, j = 0;
        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');
                    if (num > n) return false;
                    j++;
                }
                i += num;
            } else {
                if (word[i] != c) return false;
                i++;
                j++;
            }
        }
        return i == n && j == m;
    }
};

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

Edge cases to test

A number with a leading zero, including a lone "0"
A number larger than the remaining letters of word
The whole word replaced by its length, like "9" for a 9-letter word
Letters left over in word or in abbr after the other runs out

Hints

Hint 1

Walk word with one pointer and abbr with another. A letter in abbr must match the current letter of word.

Hint 2

A run of digits is one number: read it fully, reject it if it starts with '0', then jump the word pointer forward by that much.

Hint 3

The abbreviation is valid only if both pointers end exactly at the ends of their strings.

FAQ

What is the best time complexity for Valid Word Abbreviation?

Optimal (two pointers) runs in O(n + m) time and O(1) extra space. Each character of `abbr` is read once; `i` only moves forward.

Which pattern does Valid Word Abbreviation use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Valid Word Abbreviation?

Yes. Brute force (expand, then compare) takes O(n + m) time and O(n) space. Turn the abbreviation into a full-length pattern: copy letters, and replace each number by that many wildcard characters.

Which edge cases should I test for Valid Word Abbreviation?

A number with a leading zero, including a lone "0"; A number larger than the remaining letters of word; The whole word replaced by its length, like "9" for a 9-letter word; Letters left over in word or in abbr after the other runs out.