How to Check Valid Word Abbreviation in C++?

  • 时间:2020-09-27 14:36:16
  • 分类:网络文摘
  • 阅读:80 次

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) —

推荐阅读:
乙将比丙领先多少米?  求两袋糖的重量之和  两家相距有多远?  熊掌号:博客优化的SEO技巧有哪些?  超级排名系统介绍 快速提升百度搜狗360神马手机网站排名  超级排名系统:常见的搜索引擎指令有哪些?  网站是靠什么途径赚钱的?怎么让你的网站赚钱?  个人站长如何赚钱?淘宝客还是卖广告位  一道往返问题  速算小诀窍 
评论列表
添加评论