408 Valid Word Abbreviation

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.

分析& 代码

来看一题水平吊打的题

自己的方法，就是一个一个match咯&

当word和abbr都没有走到尽头：

　　如果当前位上的字母相等，那么i++, j++, continue;

　　如果abbr当前位置上的不是数字（因为之前如果是字母已经完成了匹配了），就返回false

　　如果找到abbr上的数字，i+=num

退出时候看是不是i,j都正好走到了头

需要注意的就是可能会出现Invalid的数字，比如01这样，就是一个数字必须是[1-9]\d*。

public boolean validWordAbbreviation(String word, String abbr) {
    if(word == null || abbr == null) {
        return false;
    }
    int i = 0;
    int j = 0;
    while(i < word.length() && j < abbr.length()) {
        if(word.charAt(i) == abbr.charAt(j)) {
            i++;
            j++;
            continue;
        }
        if(abbr.charAt(j) < '0' || abbr.charAt(j) > '9') {
            return false;
        }
        int start = j;
        while(j < abbr.length() && abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
            j++;
        }
        String numStr = abbr.substring(start, j);
        if(numStr.charAt(0) == '0') {
            return false;
        }
        int num = Integer.parseInt(numStr);
        i += num;
    }
    return i == word.length() && j == abbr.length();
}

然后以下是Stefan Pochmann大神做的……吊打哈哈

即把"i12iz4n"这样的缩写转换成"i.{12}iz.{4}n"

public boolean validWordAbbreviation(String word, String abbr) {
     return word.matches(abbr.replaceAll("[1-9]\\d*", ".{$0}"));
}

微笑脸…………:)

大概也就差了一个次元吧