Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Valid Word Abbreviation

Try it yourself
EasyProblemExternal link

Description

A word can be abbreviated by replacing stretches of it with their lengths. The stretches can't be empty or next to each other, and a length can't have leading zeros.

For example, "substitution" can be abbreviated as:

  • "s10n" (s, 10 letters, n)
  • "sub4u4"
  • "12" (all of it)
  • "su3i1u2on"
  • "substitution" (nothing replaced)

These are not valid: "s55n" (two stretches side by side would read as one number, 55), "s010n" (a leading zero) and "s0ubstitution" (an empty stretch).

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

Examples

Example 1

Input: word = "internationalization", abbr = "i12iz4n"

Output: true

Explanation: i, then 12 skipped letters (nternational), then i and z, then 4 skipped letters (atio), then n. Every letter lines up and both strings end together: true.

Example 2

Input: word = "apple", abbr = "a2e"

Output: false

Explanation: a matches, then 2 letters (pp) are skipped. The abbreviation then wants an e, but the word has an l: false.

Example 3

Input: word = "substitution", abbr = "s010n"

Output: false

Explanation: "010" starts with a 0, and a number in an abbreviation can't have a leading zero: false, even though skipping 10 letters would land on the n.

Constraints

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

Editorial

Brute Force

Intuition

Write the abbreviation out in full: keep each letter, and turn each number into that many ? placeholders. If the result is as long as the word and every non-? letter matches the word's letter in the same place, the abbreviation is valid.

Two checks keep it honest: a number starting with 0 is invalid on its own, and a number that can't fit in what's left of the word means false right away.

Step-by-Step Explanation

Let's trace word = "internationalization", abbr = "i12iz4n":

  1. Write it out: i, 12 × ?, i, z, 4 × ?, n.
  2. That's 20 characters, the same as the word.
  3. Compare position by position: the i, i, z and n all match; the ?s match anything.
  4. The answer is true.

Write the Abbreviation Out — Letters stay, numbers become that many '?'; then the written-out copy is compared with the word.

Algorithm

  1. Build expanded: for each letter of abbr, append it; for each number, return false if it starts with 0 or can't fit, else append that many ?.
  2. Return false if expanded and word differ in length.
  3. Return true if every non-? character of expanded equals the word's character at the same place.

Code

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        string expanded;                          // the abbreviation written out: '?' for each skipped letter
        int k = 0;
        while (k < (int)abbr.size()) {
            if (isdigit(abbr[k])) {
                if (abbr[k] == '0') return false;  // a number can't start with 0 (or be 0)
                long long num = 0;
                while (k < (int)abbr.size() && isdigit(abbr[k])) num = num * 10 + (abbr[k++] - '0');
                if ((long long)expanded.size() + num > (long long)word.size()) return false;   // it can't fit
                expanded.append(num, '?');
            } else {
                expanded += abbr[k++];
            }
        }
        if (expanded.size() != word.size()) return false;
        for (int i = 0; i < (int)word.size(); i++) {
            if (expanded[i] != '?' && expanded[i] != word[i]) return false;
        }
        return true;
    }
};

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        expanded = []                     # the abbreviation written out: '?' for each skipped letter
        k = 0
        while k < len(abbr):
            if abbr[k].isdigit():
                if abbr[k] == "0":        # a number can't start with 0 (or be 0)
                    return False
                num = 0
                while k < len(abbr) and abbr[k].isdigit():
                    num = num * 10 + int(abbr[k])
                    k += 1
                if len(expanded) + num > len(word):   # it can't fit: don't build billions of '?'
                    return False
                expanded.extend("?" * num)
            else:
                expanded.append(abbr[k])
                k += 1
        if len(expanded) != len(word):
            return False
        return all(e == "?" or e == w for e, w in zip(expanded, word))

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        StringBuilder expanded = new StringBuilder();   // the abbreviation written out: '?' for each skipped letter
        int k = 0;
        while (k < abbr.length()) {
            char c = abbr.charAt(k);
            if (Character.isDigit(c)) {
                if (c == '0') return false;             // a number can't start with 0 (or be 0)
                long num = 0;
                while (k < abbr.length() && Character.isDigit(abbr.charAt(k))) num = num * 10 + (abbr.charAt(k++) - '0');
                if (expanded.length() + num > word.length()) return false;   // it can't fit
                for (long q = 0; q < num; q++) expanded.append('?');
            } else {
                expanded.append(c);
                k++;
            }
        }
        if (expanded.length() != word.length()) return false;
        for (int i = 0; i < word.length(); i++) {
            if (expanded.charAt(i) != '?' && expanded.charAt(i) != word.charAt(i)) return false;
        }
        return true;
    }
}

var validWordAbbreviation = function(word, abbr) {
    let expanded = '';                    // the abbreviation written out: '?' for each skipped letter
    let k = 0;
    while (k < abbr.length) {
        if (abbr[k] >= '0' && abbr[k] <= '9') {
            if (abbr[k] === '0') return false;   // a number can't start with 0 (or be 0)
            let num = 0;
            while (k < abbr.length && abbr[k] >= '0' && abbr[k] <= '9') num = num * 10 + (abbr.charCodeAt(k++) - 48);
            if (expanded.length + num > word.length) return false;   // it can't fit
            expanded += '?'.repeat(num);
        } else {
            expanded += abbr[k++];
        }
    }
    if (expanded.length !== word.length) return false;
    for (let i = 0; i < word.length; i++) {
        if (expanded[i] !== '?' && expanded[i] !== word[i]) return false;
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n + m)

The written-out copy is at most as long as the word (n), and the abbreviation (m) is read once.

Space Complexity: O(n)

The written-out copy.

Why This Approach Is Not Efficient

It builds a copy as long as the word just to skip most of it. And the can't fit check isn't optional: an abbreviation can be "2147483647", and without the check that's a request for over two billion ? characters.

The ?s are never compared with anything: they only push the word's position forward. So don't write them at all. Keep one pointer in each string, and when the abbreviation has a number, jump the word's pointer forward by it.

Optimal Approach - Two Pointers

Intuition

Put i in the word and j in the abbreviation, both at 0.

  • If abbr[j] is a letter, it must equal word[i]; then both move one step.
  • If it's a digit, read the whole number first ("12" is twelve, not one and two), refusing a leading 0. Then move i forward by that number, without looking at the letters it skips.

When either pointer runs out, the abbreviation is valid only if both reached their ends together.

Step-by-Step Explanation

Let's trace word = "internationalization", abbr = "i12iz4n":

  1. word[0] = 'i' matches abbr[0]: i = 1, j = 1.
  2. abbr[1..2] is the number 12: i jumps from 1 to 13; j = 3.
  3. word[13] = 'i' matches abbr[3]: i = 14, j = 4.
  4. word[14] = 'z' matches abbr[4]: i = 15, j = 5.
  5. abbr[5] is the number 4: i jumps from 15 to 19; j = 6.
  6. word[19] = 'n' matches abbr[6]: i = 20, j = 7.

Both pointers are at their ends (20 and 7): true.

Two Pointers, With Jumps — Letters move both pointers; a number makes the word's pointer jump over that many letters.

Algorithm

  1. Set i = 0 and j = 0.
  2. While i < len(word) and j < len(abbr):
    • if abbr[j] is a digit: return false if it's 0; read the whole number into num; add num to i;
    • else: return false if word[i] != abbr[j]; add 1 to both.
  3. Return whether i == len(word) and j == len(abbr).

Code

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;                     // i in word, j in abbr
        while (i < (int)word.size() && j < (int)abbr.size()) {
            if (abbr[j] >= '0' && abbr[j] <= '9') {
                if (abbr[j] == '0') return false;   // a number can't start with 0 (or be 0)
                int num = 0;
                while (j < (int)abbr.size() && abbr[j] >= '0' && abbr[j] <= '9') {
                    num = num * 10 + (abbr[j] - '0');
                    j++;
                }
                i += num;                     // skip that many letters of word
            } else {
                if (word[i] != abbr[j]) return false;
                i++;
                j++;
            }
        }
        return i == (int)word.size() && j == (int)abbr.size();   // both must end together
    }
};

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i = j = 0                         # i in word, j in abbr
        while i < len(word) and j < len(abbr):
            if abbr[j].isdigit():
                if abbr[j] == "0":        # a number can't start with 0 (or be 0)
                    return False
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    j += 1
                i += num                  # skip that many letters of word
            else:
                if word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
        return i == len(word) and j == len(abbr)   # both must end together

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, j = 0;                     // i in word, j in abbr
        while (i < word.length() && j < abbr.length()) {
            char c = abbr.charAt(j);
            if (c >= '0' && c <= '9') {
                if (c == '0') return false;   // a number can't start with 0 (or be 0)
                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;                     // skip that many letters of word
            } else {
                if (word.charAt(i) != c) return false;
                i++;
                j++;
            }
        }
        return i == word.length() && j == abbr.length();   // both must end together
    }
}

var validWordAbbreviation = function(word, abbr) {
    let i = 0, j = 0;                     // i in word, j in abbr
    while (i < word.length && j < abbr.length) {
        if (abbr[j] >= '0' && abbr[j] <= '9') {
            if (abbr[j] === '0') return false;   // a number can't start with 0 (or be 0)
            let num = 0;
            while (j < abbr.length && abbr[j] >= '0' && abbr[j] <= '9') {
                num = num * 10 + (abbr.charCodeAt(j) - 48);
                j++;
            }
            i += num;                     // skip that many letters of word
        } else {
            if (word[i] !== abbr[j]) return false;
            i++;
            j++;
        }
    }
    return i === word.length && j === abbr.length;   // both must end together
};

Complexity Analysis

Time Complexity: O(m)

Every pass of the loop uses up at least one character of the abbreviation, and a jump costs one step however far it goes; the skipped letters are never visited.

Space Complexity: O(1)

Two indexes and the number being read.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Accepting a number that starts with 0. (no if abbr[j] == "0": return False)

On word = "a", abbr = "01" it returns true; the answer is false. "01" and "0" aren't valid numbers in an abbreviation: a leading zero is not allowed, and 0 would replace an empty stretch. Without that check, they're read as 1 and 0 and quietly accepted.

Only checking that the abbreviation ended. return j == len(abbr)

On word = "ab", abbr = "1" it returns true; the answer is false. The loop stops when either string runs out. Checking only j == len(abbr) accepts an abbreviation that runs out early, with letters of the word left over. Both have to end together.

Reading each digit as its own number. num = int(abbr[j])

On word = "abcdefghij", abbr = "10" it returns false; the answer is true. A run of digits is one number: "10" means skip ten letters, not skip one and then zero. Read the whole run before jumping.

Where This Pattern Is Taught

This problem practises two pointers on two inputs, where one pointer can jump. It's taught in Two Pointers on Two Arrays or Strings.