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) —
推荐阅读:讳辩原文及翻译 圬者王承福传原文及翻译 师说原文及翻译 杂说:马说原文及翻译 杂说:龙说原文及翻译 获麟解原文及翻译 原毁原文及翻译 你的生日是星期几 分钱的数学问题 加法原理和乘法原理练习题
- 评论列表
-
- 添加评论