0408.md

408. Valid Word Abbreviation

Level:

Topic:

Question

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Intuition

• no need to check adjacent integer, they can combine as an integer
• if sees first integer, check if it's zero, otherwise keep expanding until no integer

Two Pointer Approach

1. when sees the integer's first index keep a left and right pointer and parse to integer
2. after parsing, move the pointer at word + the integer and compare

Code

Time: O(word.length)
Space: O(1)

public boolean validWordAbbreviation(String word, String abbr) {

    int p1 = 0, p2 = 0;
    int start = 0;
    while (p1 < word.length() && p2 < abbr.length()) {
        char c = abbr.charAt(p2);
        if (word.charAt(p1) != c) {
            if (Character.isDigit(c)) {
                if (c == '0')
                    return false;
                start = p2;
                while (p2 < abbr.length() && Character.isDigit(abbr.charAt(p2)))
                    p2++;
                int n = Integer.parseInt(abbr.substring(start, p2));
                p1 += n;
            } else
                return false;
        } else {
            p1++;
            p2++;
        }
    }
    return p1 == word.length() && p2 == abbr.length();
}