valid-word-abbreviation

Valid Word Abbreviation – LeetCode 408

Problem

Description

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”.

Answer

Original

Code

class Solution {
public:
    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;
    }
};

思路

简单的双指针循环遍历比较，需要注意的是abbr中的数字可能由多位组成，时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。