LeetCode 408 - Valid Word Abbreviation

http://bookshadow.com/weblog/2016/10/02/leetcode-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://discuss.leetcode.com/topic/61348/short-and-easy-to-understand-java-solution

    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, 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;
            }
            int num = Integer.valueOf(abbr.substring(start, j));
            i += num;
        }
        return i == word.length() && j == abbr.length();
    }

https://blog.csdn.net/qq508618087/article/details/52774037
    bool validWordAbbreviation(string word, string abbr) {
        int k = 0, i = 0, len1 = word.size(), len2 = abbr.size();
        while(i < len2)
        {
            if(word[k]==abbr[i]) { i++, k++; continue; }
            int cnt = 0;
            if(abbr[i] == '0') return false;
            while(isdigit(abbr[i]))
               cnt = cnt*10 + (abbr[i]-'0'), i++;
            k += cnt;
            if(k > len1 || word[k] != abbr[i]) return false;
        }
        return k==len1;
    }
https://discuss.leetcode.com/topic/61362/simple-java-code-with-two-pointers
Use two pointers to track the start of the word and abbr. Move abbr pointer, change word pointer accordingly, check whether we can get to the end of word

模拟题，遍历word和abbr即可
def validWordAbbreviation(self, word, abbr): """ :type word: str :type abbr: str :rtype: bool """ size = len(word) cnt = loc = 0 for w in abbr: if w.isdigit(): if w == '0' and cnt == 0: return False cnt = cnt * 10 + int(w) else: loc += cnt cnt = 0 if loc >= size or word[loc] != w: return False loc += 1 return loc + cnt == size
http://www.cnblogs.com/grandyang/p/5930369.html

    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0, m = word.size(), n = abbr.size();
        while (i < m && j < n) {
            if (abbr[j] >= '0' && abbr[j] <= '9') {
                if (abbr[j] == '0') return false;
                int val = 0;
                while (j < n && abbr[j] >= '0' && abbr[j] <= '9') {
                    val = val * 10 + abbr[j++] - '0';
                }
                i += val;
            } else {
                if (word[i++] != abbr[j++]) return false;
            }
        }
        return i == m && j == n;
    }

下面这种方法和上面的方法稍有不同，这里是用了一个for循环来遍历缩写单词的所有字符，然后用一个指针p来指向与其对应的原单词的位置，然后cnt表示当前读取查出来的数字，如果读取的是数字，我们先排除首位是0的情况，然后cnt做累加；如果读取的是字母，那么指针p向后移动cnt位，如果p到超过范围了，或者p指向的字符和当前遍历到的缩写单词的字符不相等，则返回false，反之则给cnt置零继续循环，参见代码如下：

    bool validWordAbbreviation(string word, string abbr) {
        int m = word.size(), n = abbr.size(), p = 0, cnt = 0;
        for (int i = 0; i < abbr.size(); ++i) {
            if (abbr[i] >= '0' && abbr[i] <= '9') {
                if (cnt == 0 && abbr[i] == '0') return false;
                cnt = 10 * cnt + abbr[i] - '0';
            } else {
                p += cnt;
                if (p >= m || word[p++] != abbr[i]) return false;
                cnt = 0;
            }
        }
        return p + cnt == m;
    }

X. Use Regular Expression
https://discuss.leetcode.com/topic/61353/simple-regex-one-liner-java-python
I just turn an abbreviation like "i12iz4n" into a regular expression like "i.{12}iz.{4}n"

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