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:
Input: word = "internationalization", abbr = "i12iz4n" Output: true Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").
Example 2:
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.
Solutions
Solution 1: Simulation
We can directly simulate character matching and replacement.
Assume the lengths of the string $word$ and the string $abbr$ are $m$ and $n$ respectively. We use two pointers $i$ and $j$ to point to the initial positions of the string $word$ and the string $abbr$ respectively, and use an integer variable $x$ to record the current matched number in $abbr$.
Loop to match each character of the string $word$ and the string $abbr$:
If the character $abbr[j]$ pointed by the pointer $j$ is a number, if $abbr[j]$ is '0'
and $x$ is $0$, it means that the number in $abbr$ has leading zeros, so it is not a valid abbreviation, return false
; otherwise, update $x$ to $x \times 10 + abbr[j] - '0'$.
If the character $abbr[j]$ pointed by the pointer $j$ is not a number, then we move the pointer $i$ forward by $x$ positions at this time, and then reset $x$ to $0$. If $i \geq m$ or $word[i] \neq abbr[j]$ at this time, it means that the two strings cannot match, return false
; otherwise, move the pointer $i$ forward by $1$ position.
Then we move the pointer $j$ forward by $1$ position, repeat the above process, until $i$ exceeds the length of the string $word$ or $j$ exceeds the length of the string $abbr$.
Finally, if $i + x$ equals $m$ and $j$ equals $n$, it means that the string $word$ can be abbreviated as the string $abbr$, return true
; otherwise return false
.
The time complexity is $O(m + n)$, where $m$ and $n$ are the lengths of the string $word$ and the string $abbr$ respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|