408. Valid Word Abbreviation

Posted on Edited on In

408. Valid Word Abbreviation

Description

A string can be abbreviated by replacing any number of non-adjacent , non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

  • "s10n" ("s ubstitutio n")
  • "sub4u4" ("sub stit u tion")
  • "12" ("substitution")
  • "su3i1u2on" ("su bst i t u ti on")
  • "substitution" (no substrings replaced)

The following are not valid abbreviations:

  • "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
  • "s010n" (has leading zeros)
  • "s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

1
2
3
Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Example 2:

1
2
3
Input: word = "apple", abbr = "a2e"
Output: false
Explanation: The word "apple" cannot be abbreviated as "a2e".

Constraints:

  • 1 <= word.length <= 20
  • word consists of only lowercase English letters.
  • 1 <= abbr.length <= 10
  • abbr consists of lowercase English letters and digits.
  • All the integers in abbr will fit in a 32-bit integer.

Hints/Notes

  • 2025/01/14
  • premium and no leetcode solution

Solution

Language: C++

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
class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int m = word.size(), n = abbr.size(), j = 0;
        for (int i = 0; i < n; ) {
            if (isalpha(abbr[i])) {
                if (j >= word.size() || abbr[i++] != word[j++]) {
                    return false;
                }
            } else {
                if (abbr[i] == '0') {
                    return false;
                }
                int start = i;
                while (i < n && isdigit(abbr[i])) {
                    i++;
                }
                j += stoi(abbr.substr(start, i - start));
                if (j > m) {
                    return false;
                }
            }
        }
        return j == m;
    }
};