Valid Word Abbreviation

Valid Word Abbreviation tests something simple but tricky. You read a string that mixes letters and numbers. The numbers mean “skip this many letters”. The interviewer wants to see if you can parse a number out of a string and move two markers carefully. Small off-by-one mistakes here are common, so care matters.

🎯 The Problem

You get a full word and a short abbreviation. You return true if the abbreviation describes the word, and false if it does not.

The rules:

• The abbreviation can hold letters and numbers.
• A number means skip that many letters in the word.
• A letter must match the word exactly at that spot.
• A number must not start with zero, so 05 is not allowed.

For "internationalization" and "i12iz4n": the i matches, 12 skips twelve letters, i matches, z matches, 4 skips four letters, and n matches the last letter. So it is valid.

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

Explanation: i, skip 12, i, z, skip 4, n -> lines up exactly with the word.

Here is what the abbreviation is telling us to do, step by step.

🐢 Approach 1: Expand The Abbreviation (Brute Force)

The idea in one line: build the full word from the abbreviation, then compare it letter by letter.

The idea:

• Turn every number into that many filler marks.
• Build a whole new string from the short form.
• Compare lengths and check the letters line up.

How it works:

• Walk the abbreviation and write out filler marks for each number.
• Then match the built string against the word.

Why it is weak:

• You build a whole new string just to throw it away after the check.
• The word expand means turning the short form back into a long form.
• A giant number like 1000 makes a thousand filler marks. That is a lot of memory for nothing.

Here is the expansion code for that idea:

def valid_word_abbreviation(word, abbr):
    expanded = []
    i = 0

    while i < len(abbr):
        if abbr[i].isdigit():
            if abbr[i] == "0":
                return False
            number = 0
            while i < len(abbr) and abbr[i].isdigit():
                number = number * 10 + int(abbr[i])
                i += 1
            expanded.extend(["*"] * number)
        else:
            expanded.append(abbr[i])
            i += 1

    return len(expanded) == len(word) and all(a == "*" or a == w for a, w in zip(expanded, word))

⚡ Approach 2: Two Pointers (Best)

The idea in one line: keep one pointer on the word and one on the abbreviation, then walk both at the same time. A pointer is just an index that says where you are in a string.

The idea:

• One pointer on the word. One pointer on the abbreviation.
• A letter must match. A number means skip ahead.
• Move the two pointers at different speeds.

How it works:

• Abbreviation has a letter: compare it to the word at the word pointer. Match moves both. No match returns false.
• Abbreviation has a digit: read the whole number, since it can be many digits like 12. Then jump the word pointer forward by that number.
• A number must not start with zero, so 01 returns false.

Why it is fast:

• It reads each character once and never builds an extra string, so time is O(n).
• It keeps only a couple of index variables, so space is O(1).
• At the end, both pointers must land at the end together. If one finishes early, the answer is false.

Here is the two-pointer walk on the example.

Steps to Solve

1. Set a word pointer and an abbreviation pointer, both at zero.
2. Walk while the abbreviation pointer has characters left.
3. If the current abbreviation character is a digit, check it is not a leading zero. If it is zero at the start of a number, return false.
4. Read the full number, then jump the word pointer forward by that number.
5. If the current abbreviation character is a letter, compare it to the word at the word pointer. If they differ, or the word pointer is past the end, return false. Otherwise move both pointers.
6. At the end, return true only if both pointers reached the end of their strings.

#include <stdio.h>
#include <string.h>

int validAbbreviation(const char *word, const char *abbr) {
    int wp = 0, ap = 0;
    int wlen = strlen(word), alen = strlen(abbr);
    while (ap < alen) {
        if (abbr[ap] >= '0' && abbr[ap] <= '9') {
            if (abbr[ap] == '0') return 0;     // leading zero not allowed
            int num = 0;
            while (ap < alen && abbr[ap] >= '0' && abbr[ap] <= '9') {
                num = num * 10 + (abbr[ap] - '0'); // build the number
                ap++;
            }
            wp += num;                         // jump the word pointer
        } else {
            if (wp >= wlen || word[wp] != abbr[ap]) return 0; // letter must match
            wp++;
            ap++;
        }
    }
    return wp == wlen;                          // both must end together
}

int main(void) {
    const char *word = "internationalization";
    const char *abbr = "i12iz4n";
    printf("%s\n", validAbbreviation(word, abbr) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool validAbbreviation(string word, string abbr) {
    int wp = 0, ap = 0;
    int wlen = word.size(), alen = abbr.size();
    while (ap < alen) {
        if (isdigit(abbr[ap])) {
            if (abbr[ap] == '0') return false;   // leading zero not allowed
            int num = 0;
            while (ap < alen && isdigit(abbr[ap])) {
                num = num * 10 + (abbr[ap] - '0'); // build the number
                ap++;
            }
            wp += num;                           // jump the word pointer
        } else {
            if (wp >= wlen || word[wp] != abbr[ap]) return false; // must match
            wp++;
            ap++;
        }
    }
    return wp == wlen;                            // both must end together
}

int main() {
    cout << (validAbbreviation("internationalization", "i12iz4n") ? "true" : "false") << endl;
    return 0;
}

true

public class ValidWordAbbreviation {
    public static boolean validAbbreviation(String word, String abbr) {
        int wp = 0, ap = 0;
        int wlen = word.length(), alen = abbr.length();
        while (ap < alen) {
            char c = abbr.charAt(ap);
            if (Character.isDigit(c)) {
                if (c == '0') return false;        // leading zero not allowed
                int num = 0;
                while (ap < alen && Character.isDigit(abbr.charAt(ap))) {
                    num = num * 10 + (abbr.charAt(ap) - '0'); // build the number
                    ap++;
                }
                wp += num;                         // jump the word pointer
            } else {
                if (wp >= wlen || word.charAt(wp) != c) return false; // must match
                wp++;
                ap++;
            }
        }
        return wp == wlen;                         // both must end together
    }

    public static void main(String[] args) {
        System.out.println(validAbbreviation("internationalization", "i12iz4n"));
    }
}

true

def valid_abbreviation(word, abbr):
    wp, ap = 0, 0                      # word pointer, abbr pointer
    while ap < len(abbr):
        if abbr[ap].isdigit():
            if abbr[ap] == "0":        # leading zero is not allowed
                return False
            num = 0
            while ap < len(abbr) and abbr[ap].isdigit():
                num = num * 10 + int(abbr[ap])  # build the full number
                ap += 1
            wp += num                  # jump the word pointer forward
        else:
            if wp >= len(word) or word[wp] != abbr[ap]:  # letter must match
                return False
            wp += 1
            ap += 1
    return wp == len(word)             # both must finish together


print(valid_abbreviation("internationalization", "i12iz4n"))

True

function validAbbreviation(word, abbr) {
  let wp = 0, ap = 0; // word pointer, abbr pointer
  while (ap < abbr.length) {
    const c = abbr[ap];
    if (c >= "0" && c <= "9") {
      if (c === "0") return false;       // leading zero not allowed
      let num = 0;
      while (ap < abbr.length && abbr[ap] >= "0" && abbr[ap] <= "9") {
        num = num * 10 + Number(abbr[ap]); // build the number
        ap++;
      }
      wp += num;                         // jump the word pointer
    } else {
      if (wp >= word.length || word[wp] !== c) return false; // must match
      wp++;
      ap++;
    }
  }
  return wp === word.length;             // both must end together
}

console.log(validAbbreviation("internationalization", "i12iz4n"));

true

Let us walk through the Python version line by line, because the pointer moves are the whole trick.

wp, ap = 0, 0 sets both pointers to the start. wp is on the word and ap is on the abbreviation. We move them at different speeds, which is why we keep two.

while ap < len(abbr): runs until we have read the whole abbreviation. We drive the loop off the abbreviation because that is the thing telling us what to do.

if abbr[ap].isdigit(): checks if we are looking at a number. The isdigit returns true for 0 through 9. If it is a digit, we are about to skip letters.

if abbr[ap] == "0": return False rejects a leading zero. A number like 05 is invalid. We check this before reading the number so we catch it early.

while ap < len(abbr) and abbr[ap].isdigit(): reads every digit of the number. A number can be many digits, like 12. We keep going until the digits stop.

num = num * 10 + int(abbr[ap]) builds the number digit by digit. We multiply by ten and add the new digit. So 1 then 2 becomes 12. This is how you turn a digit string into a real number.

wp += num jumps the word pointer forward by the number. This is the skip. We never look at those letters. We just step over them.

if wp >= len(word) or word[wp] != abbr[ap]: return False handles a letter. The letter must match the word at the word pointer. We also check wp did not run off the end, because the skip might have pushed it too far.

return wp == len(word) is the final check. Both pointers must land at the end together. If the word pointer stopped short or went past, the abbreviation did not describe the word, so we return false.

⏱️ Time and Space Complexity

The expand approach builds a whole new string, so it can blow up with a big number inside the abbreviation. The two-pointer scan reads each character once and never builds anything extra. So it runs in O(n) time, where n is the longer of the two strings. And it uses only a couple of index variables, so the space is O(1). That makes the two-pointer scan the clear pick.

🧩 Key Takeaways

• ✅ Keep two pointers, one on the word and one on the abbreviation, and move them together.
• ✅ A number means skip that many letters, so jump the word pointer forward by it.
• ✅ A letter must match the word exactly, or the answer is false.
• ✅ Reject a number that starts with zero, like 05.
• ✅ At the end, both pointers must reach the end of their strings.

🚀 What’s Next?

• Custom Sort String
• Integer to English Words