408. Valid Word Abbreviation

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.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

Solution:

To determine whether an abbreviation is valid, we use two pointers point to the start of two stings.

If we find a number in string abbr, we advance the pointer and update the shift value.

Notice that if we meet leading zero, this abbr is invalid.

When the pointer points to a non-zero character, we update the pointer in string s with shift steps.

We compare the characters point by the two pointers.

If they are equal, we advance both pointers.

Otherwise the string abbr is invalid.

Finally we check wether both of the pointers are at the end of their strings.

The time complexity is O(n) and the space complexity is O(n).



Code:

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