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.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

第零位长度就是1了，指针要先加再给 ++i 提前加一 , 需要再次控制范围：j < abbr.length() 否则会不自觉溢出
此题特殊：j所在数字为0也不行，01会返回true
```
"a"
"01"
```

［思维问题］：

有两个单词居然会想不出两个指针吗？

［一句话思路］：

没数字时一直走，走到有数字时再开始统计

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

两个单词就用两个指针，两个起点

［复杂度］：Time complexity: O() Space complexity: O()

［英文数据结构或算法，为什么不用别的数据结构或算法］：

ASCII码表的顺序是（按二进制排序）：数字-大写字母-小写字母

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

527. Word Abbreviation 自制单词压缩：要排序

411. Minimum Unique Word Abbreviation 排列组合找出第一个单词的所有缩写：回溯法

[代码风格] ：

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        //ini
        int i = 0, j = 0;
        
        //while loop
        while (i < word.length() && j < abbr.length()) {
            //if letters, go on
            if (word.charAt(i) == abbr.charAt(j)) {
                ++i;
                ++j;
                continue;
            }
            //cc, first num shouldn't be 0
            if (abbr.charAt(j) <= '0' || abbr.charAt(j) > '9') return false;
            //substring of j
            int start = j;
            //control j whenever
            while (j < abbr.length() && abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
                ++j;
            }
            int num = Integer.valueOf(abbr.substring(start, j));
            //add to i
            i += num;
        }
        
        //return
        return (i == word.length()) && (j == abbr.length());
    }
}

View Code