Sunday, October 23, 2016

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.

Using two pointers, one for word, the other for abbreviation. If the pointer for abbreviation points a char that is a number, check first if its 0. Then get the whole number and check if it exceeds word's length. If the pointer points a char that is a letter, check if it's equal to the one in word.


public boolean validWordAbbreviation(String word, String abbr) {
        if (word.length() == 0) {
            return abbr.length() == 0;
        }
        int pW = 0, pA = 0;
        while (pW < word.length() && pA < abbr.length()) {
            char a = abbr.charAt(pA);
            if (Character.isLetter(a)) {
                if (word.charAt(pW) != abbr.charAt(pA)) {
                    return false;
                }
                pW++;
                pA++;
            } else if (Character.isDigit(a)) {
                if (a == '0') {
                    return false;
                }
                int org = pA;
                while (pA < abbr.length() && Character.isDigit(abbr.charAt(pA))) {
                    pA++;
                }
                int num = Integer.valueOf(abbr.substring(org, pA));
                while (pW < word.length() && num > 0) {
                    pW++;
                    num--;
                }
                if (num > 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }


No comments:

Post a Comment