题目地址:https://leetcode-cn.com/problems/valid-word-abbreviation/

题目描述

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

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

题目大意

给一个非空 字符串 s 和一个单词缩写 abbr ,判断这个缩写是否可以是给定单词的缩写。

解题方法

双指针

一个指针指向abbr,一个指针指向word,根据abbr的数字情况移动word的指针,如果abbr指针指向的不是数字而是字符,那么判断是否和word字符相同。最后两个指针应该会同时移动到各自的结尾。

这个题有个小坑,就是有前导0的数字是非法的,需要判断一下。

C++代码如下:

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int iword = 0;
        int iabbr = 0;
        while (iword < word.size() && iabbr < abbr.size()) {
            int count = 0;
            if (count == 0 && abbr[iabbr] == '0')
                return false;
            while (abbr[iabbr] >= '0' && abbr[iabbr] <= '9') {
                count = 10 * count + abbr[iabbr] - '0';
                iabbr ++;
            }
            iword += count;
            if ((iword >= word.size() && iabbr != abbr.size()) || 
                (iword != word.size() && iabbr >= abbr.size()))
                return false;
            if (iword == word.size() && iabbr == abbr.size())
                return true;
            if (word[iword] != abbr[iabbr])
                return false;
            iword ++;
            iabbr ++;
        }
        return iword == word.size() && iabbr == abbr.size();
    }
};

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

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发