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

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.

Valid Word Abbreviation Algorithm in C++

One corner case is that you have leading zeros. For example, ’01’ is not a validate abbreviation of word ‘a’ but ‘1’ is. In the following C++ implementation, we have two pointers, one pointing to the original word, and the other pointing to the abbreviation. When we have digits (using isdigit() function), we need to convert them to decimal integers, and when we meet letters, we need to compare the letters at both words. Of course, we need to update the pointer locations and check if the length matches i.e. ‘w2’ is not an abbreviation of ‘word’. And ‘w9999’ is not an abbreviation of ‘word’.

The C++ implementation runs at O(N) time complexity where N is the length of the abbreviation string and it requires O(1) constant space. One typical/known test case is ‘i18n’ is a word abbreviation for “internationalization”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int len = abbr.size();
        int i = 0, j = 0;
        int cur = 0;
        while (i < len) {
            if (isdigit(abbr[i])) {
                if ((cur == 0) && (abbr[i] == '0')) { // no leading zeros in the word abbreviation
                    return false;
                }
                cur = cur * 10 + abbr[i] - '0';
            } else {
                j += cur;
                if (j >= word.size()) { // 'w999' is not abbreviation of 'word'
                    return false;
                }
                if (word[j] != abbr[i]) {
                    return false;
                }
                j ++;
                cur = 0;
            }
            ++ i;
        }
        j += cur;
        return j == word.size();
    }
};

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int len = abbr.size();
        int i = 0, j = 0;
        int cur = 0;
        while (i < len) {
            if (isdigit(abbr[i])) {
                if ((cur == 0) && (abbr[i] == '0')) { // no leading zeros in the word abbreviation
                    return false;
                }
                cur = cur * 10 + abbr[i] - '0';
            } else {
                j += cur;
                if (j >= word.size()) { // 'w999' is not abbreviation of 'word'
                    return false;
                }
                if (word[j] != abbr[i]) {
                    return false;
                }
                j ++;
                cur = 0;
            }
            ++ i;
        }
        j += cur;
        return j == word.size();
    }
};

–EOF (The Ultimate Computing & Technology Blog) —