Valid Word Abbreviation

Problem

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note: Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Examples

Examples

Example 1

```clike
Given **s** = "internationalization", **abbr** = "i12iz4n":

Return true.

#### Example 2

```d

```clike
Given **s** = "apple", **abbr** = "a2e":

Return false.

Solution

Method 1 – Two Pointers

Intuition

We use two pointers to scan both the original string and the abbreviation. When we see a digit in the abbreviation, we parse the full number and skip that many characters in the original string. Otherwise, we match characters one by one.

Approach

1. Use two pointers, one for s and one for abbr.
2. If abbr[j] is a digit, parse the full number (no leading zeros allowed), and advance i by that number.
3. If abbr[j] is a letter, check if it matches s[i].
4. If all characters are matched and both pointers reach the end, return true.

Code

C++

bool validWordAbbreviation(string word, string abbr) {
    int i = 0, j = 0, n = word.size(), m = abbr.size();
    while (i < n && j < m) {
        if (isdigit(abbr[j])) {
            if (abbr[j] == '0') return false;
            int num = 0;
            while (j < m && isdigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            i += num;
        } else {
            if (i >= n || word[i] != abbr[j]) return false;
            i++; j++;
        }
    }
    return i == n && j == m;
}

Go

import "unicode"
func validWordAbbreviation(word, abbr string) bool {
    i, j := 0, 0
    for i < len(word) && j < len(abbr) {
        if abbr[j] >= '0' && abbr[j] <= '9' {
            if abbr[j] == '0' {
                return false
            }
            num := 0
            for j < len(abbr) && abbr[j] >= '0' && abbr[j] <= '9' {
                num = num*10 + int(abbr[j]-'0')
                j++
            }
            i += num
        } else {
            if i >= len(word) || word[i] != abbr[j] {
                return false
            }
            i++
            j++
        }
    }
    return i == len(word) && j == len(abbr)
}

Java

public boolean validWordAbbreviation(String word, String abbr) {
    int i = 0, j = 0;
    while (i < word.length() && j < abbr.length()) {
        if (Character.isDigit(abbr.charAt(j))) {
            if (abbr.charAt(j) == '0') return false;
            int num = 0;
            while (j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
                num = num * 10 + (abbr.charAt(j) - '0');
                j++;
            }
            i += num;
        } else {
            if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) return false;
            i++;
            j++;
        }
    }
    return i == word.length() && j == abbr.length();
}

Kotlin

fun validWordAbbreviation(word: String, abbr: String): Boolean {
    var i = 0; var j = 0
    while (i < word.length && j < abbr.length) {
        if (abbr[j].isDigit()) {
            if (abbr[j] == '0') return false
            var num = 0
            while (j < abbr.length && abbr[j].isDigit()) {
                num = num * 10 + (abbr[j] - '0')
                j++
            }
            i += num
        } else {
            if (i >= word.length || word[i] != abbr[j]) return false
            i++
            j++
        }
    }
    return i == word.length && j == abbr.length
}

Python

def validWordAbbreviation(word: str, abbr: str) -> bool:
    i = j = 0
    while i < len(word) and j < len(abbr):
        if abbr[j].isdigit():
            if abbr[j] == '0':
                return False  # leading zero not allowed
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            i += num
        else:
            if i >= len(word) or word[i] != abbr[j]:
                return False
            i += 1
            j += 1
    return i == len(word) and j == len(abbr)

Rust

pub fn valid_word_abbreviation(word: &str, abbr: &str) -> bool {
    let (mut i, mut j) = (0, 0);
    let w = word.as_bytes();
    let a = abbr.as_bytes();
    while i < w.len() && j < a.len() {
        if a[j].is_ascii_digit() {
            if a[j] == b'0' { return false; }
            let mut num = 0;
            while j < a.len() && a[j].is_ascii_digit() {
                num = num * 10 + (a[j] - b'0') as usize;
                j += 1;
            }
            i += num;
        } else {
            if i >= w.len() || w[i] != a[j] { return false; }
            i += 1; j += 1;
        }
    }
    i == w.len() && j == a.len()
}

TypeScript

function validWordAbbreviation(word: string, abbr: string): boolean {
    let i = 0, j = 0;
    while (i < word.length && j < abbr.length) {
        if (abbr[j] >= '0' && abbr[j] <= '9') {
            if (abbr[j] === '0') return false;
            let num = 0;
            while (j < abbr.length && abbr[j] >= '0' && abbr[j] <= '9') {
                num = num * 10 + Number(abbr[j]);
                j++;
            }
            i += num;
        } else {
            if (i >= word.length || word[i] !== abbr[j]) return false;
            i++;
            j++;
        }
    }
    return i === word.length && j === abbr.length;
}

Complexity

• ⏰ Time complexity: O(N) — N is the length of abbr (and word).
• 🧺 Space complexity: O(1) — Only a few variables are used.