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.

链接：https://leetcode.com/problems/valid-word-abbreviation/#/description

3/22/2017

注意：

1. 第8行判断是否有leading的0，我认为这个属于invalid input。不过既然是google，需要仔细检查所有可能。

2. 遇到char时，index如何加，比较之后是否加。其实，在比较之后，之前inInteger的状态已经无所谓了，所以都需要+1

 1 public class Solution {
 2     public boolean validWordAbbreviation(String word, String abbr) {
 3         boolean inInteger = false;
 4         int number = 0;
 5         int index = 0;
 6         for (int i = 0; i < abbr.length(); i++) {
 7             if (Character.isDigit(abbr.charAt(i))) {
 8                 if (!inInteger && abbr.charAt(i) - '0' == 0) return false;
 9                 number = number * 10 + abbr.charAt(i) - '0';
10                 inInteger = true;
11             } else {
12                 if (inInteger) {
13                     index += number;
14                     inInteger = false;
15                     number = 0;
16                 }
17                 if (index >= word.length()) return false;
18                 if (word.charAt(index) != abbr.charAt(i)) return false;
19                 index += 1;
20             }
21         }
22         if (inInteger) {
23             index += number;
24         }
25         if (index != word.length()) return false;
26         return true;
27     }
28 }

别人的思路：

1. 每次先比较2者是否相同，若不同查abbr是否是<=0或者>9（注意这里就排除了leading 0），再记录abbr index遍历abbr直到abbr的值不为数字，同时word加上中间的间隔。下次比较可以有结论。

2. 有个外国老哥，总是有很巧妙的方法：

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

其他讨论：https://discuss.leetcode.com/category/535/valid-word-abbreviation