Solution: Valid Word Abbreviation
Let’s solve the Valid Word Abbreviation problem using Two Pointers.
We'll cover the following
Statement
Given a string word
and an abbreviation abbr
, return TRUE if the abbreviation matches the given string. Otherwise, return FALSE.
A certain word "calendar"
can be abbreviated as follows:
"cal3ar"
("cal
end
ar"
skipping three characters"end"
from the word"calendar"
still matches the provided abbreviation)"c6r"
("c
alenda
r"
skipping six characters"alenda"
from the word"calendar"
still matches the provided abbreviation)
The word "internationalization"
can also be abbreviated as "i18n"
(the abbreviation comes from skipping 18 characters in "internationalization"
, leaving the first and last letters "i"
and "n"
).
The following are not valid abbreviations:
"c06r"
(has leading zeroes)"cale0ndar"
(replaces an empty string)"c24r"
("c
al
enda
r"
the replaced are adjacent)substrings A substring is a contiguous non-empty sequence of characters within a string.
Constraints:
word.length
word
consists of only lowercase English letters.abbr.length
abbr
consists of lowercase English letters and digits.All the integers in
abbr
will fit in a–bit integer.
Solution
The idea behind this problem is to match each character in the abbreviation, abbr
, exactly to the corresponding character in the word. We incrementally iterate over both strings, ensuring they match at each step. To achieve this, we can use the two-pointer technique. We initialize one pointer to the start of the word and the other to the start of the abbreviation.
The two-pointer technique is efficient for solving this problem because it effectively helps in character matching, handling leading zero cases, and skipping the exact number of characters in word
as found in abbr
.
By maintaining these checks and iterating over both strings, we ensure that the abbreviation correctly represents the word.
Having said this, here’s the algorithm that we’ll use to solve the given problem:
We create two pointers:
wordIndex
andabbrIndex
, both initialized to. Next, we iterate through the abbreviations string while
abbrIndex
is less than the length ofabbr
:If a digit is encountered at
abbr[abbrIndex]
:We then check if that digit is a leading zero. If it is, we return FALSE.
Next, we calculate the number from
abbr
and skip that many characters inword
.
In case the value at index
abbr[abbrIndex]
is a letter:We then check for characters that match with
word[wordIndex]
. If the characters don’t match in both strings, we return FALSE.Next, we increment both
wordIndex
andabbrIndex
by.
Finally, we ensure whether both pointers,
wordIndex
andabbrIndex
, have reached the end of their strings. If they have, we return TRUE. Otherwise, we return FALSE.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.