408. Valid Word Abbreviation
Problem Description
The problem presents a method of abbreviating strings by replacing non-adjacent, non-empty substrings with the length of those substrings. The objective is to evaluate whether a given abbreviated string, abbr
, correctly represents the abbreviation of another string, word
. It's important to note that a valid abbreviation:
- replaces non-empty and non-adjacent substrings,
- does not have leading zeros in the numerical representations of the lengths,
- is not created by replacing adjacent substrings.
The goal is to determine if the given abbr
represents a valid abbreviation of the word
.
Here are some examples:
"s10n"
is a valid abbreviation of"substitution"
because the substring of 10 characters, "ubstitutio", is replaced by its length, without leading zeros."s55n"
is not valid because it implies adjacent substrings were replaced, which is against the rules.
We are tasked with writing a function that takes word
and abbr
and returns True
if abbr
is a valid abbreviation of word
, and False
otherwise.
Intuition
The solution is implemented by simultaneously iterating through both word
and abbr
and checking for matches and valid abbreviations. The approach is as follows:
- Iterate over each character in the
word
using a pointeri
and a pointerj
for iterating over theabbr
. - If the current characters in
word
andabbr
match, continue to the next characters of both strings. - If the current character in
abbr
is a digit, it indicates an abbreviated part ofword
. We then:- Check for any leading zeros or if the number is '0', which are not valid.
- Parse the complete number indicating the length of the abbreviated substring.
- Skip ahead in
word
by the length of the abbreviated part.
- After the loop:
- If
i
is at the end ofword
andj
is at the end ofabbr
, the abbreviation is valid, and we returnTrue
. - If either
i
is not at the end ofword
orj
is not at the end ofabbr
, the abbreviation is not valid, and we returnFalse
.
- If
We leverage the facts that letters must match exactly and numbers must accurately represent the length of the skipped substrings in the word
.
This approach efficiently determines if the abbreviation is valid by inspecting each character only once, resulting in an O(n) time complexity, where n is the length of the word
.
Learn more about Two Pointers patterns.
Solution Approach
The solution uses a straightforward approach based on two-pointer iteration and string manipulation techniques without the need for additional data structures. Let's walk through the implementation and the reasoning behind it:
- Two integer pointers,
i
andj
, are initialized to0
. These act as indexes to traverseword
andabbr
respectively. - Two variables,
m
andn
, hold the lengths ofword
andabbr
. They help in checking whether we have reached the end of the strings during iteration.
The algorithm then enters a while-loop, with the condition that i
is less than m
, letting us loop until the end of word
:
-
The first
if
statement within the loop checks whetherj
has reached the end ofabbr
. If it has, thenabbr
cannot be a valid abbreviation ofword
because there are unmatched characters inword
, so the function returnsFalse
. -
If
word[i]
is equal toabbr[j]
, we have a direct character match, and we advance both pointers. -
If
word[i]
is not equal toabbr[j]
, the algorithm checks for a number inabbr
by entering another while-loop which continues as long asabbr[k]
is a digit. This is determined by theisdigit()
method, effectively parsing an integer from the abbreviation. -
After exit from the inner while-loop, a substring
t
fromabbr[j]
toabbr[k]
holds the number. -
The validity of the number is then checked:
- It should be a digit and not have leading zeros.
- It should not be
0
since an abbreviation can't represent a substring of0
length.
-
If
t
is valid, the lengthint(t)
is added to pointeri
to skip the matching characters inword
. Pointerj
is set tok
to continue checkingabbr
after the number.
Finally, after the while-loop:
- The function returns
True
only ifi == m
andj == n
, meaning that both the word and abbreviation were completely matched.
Overall, the solution uses an iterative approach and basic string operations without requiring additional memory, i.e., in O(1) space complexity, and time complexity is O(n), where n is the length of the word
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach described in the content above. Suppose we have the word "international"
and the abbreviation "i11l"
. We want to determine if "i11l"
is a correct abbreviation for "international"
.
Here's the step-by-step process of checking the validity of the abbreviation:
-
Initialize two pointer variables,
i
andj
, to0
. They will iterate over the characters in"international"
and"i11l"
, respectively. -
Iterate while
i < len("international")
.-
Step 1: Both
i
andj
point to'i'
. Since the characters match, we movei
andj
forward to1
. -
Step 2:
j
now points to'1'
. This signifies an abbreviation. Since'1'
is a digit and not'0'
, there are no leading zeros, and so it is initially considered valid. -
Step 3: We continue to move
j
forward to gather the complete number representing the length of the abbreviation. We find thatj
is'1'
at index1
and'1'
at index2
. This represents the number11
. -
Step 4: After parsing the complete number
11
, we move thei
pointer forward in"international"
by11
characters, landing it on'l'
. -
Step 5: We set
j
to the index after the parsed number, which is3
, pointing to'l'
.
-
-
Now, both
i
andj
point to'l'
again, which match, so we move bothi
andj
forward by1
. -
At this point,
i == len("international")
andj == len("i11l")
, indicating that we have reached the end of both the word and the abbreviation. Since all characters have been successfully matched, and the numerical abbreviations have been valid, we returnTrue
.
So, "i11l"
is a valid abbreviation for "international"
.
Solution Implementation
1class Solution:
2 def validWordAbbreviation(self, word: str, abbr: str) -> bool:
3 # Initialize pointers for word and abbreviation
4 word_index = 0
5 abbr_index = 0
6
7 # Get lengths of word and abbreviation
8 word_length = len(word)
9 abbr_length = len(abbr)
10
11 # Loop through the characters in the word
12 while word_index < word_length:
13 # Check if abbreviation index has become out of bound
14 if abbr_index >= abbr_length:
15 return False
16
17 # If current characters match, move to the next ones
18 if word[word_index] == abbr[abbr_index]:
19 word_index += 1
20 abbr_index += 1
21 continue
22
23 # Check if abbreviation character is not a digit
24 if not abbr[abbr_index].isdigit():
25 return False
26
27 # Calculate the number representing the skipped characters
28 num_start_index = abbr_index
29 while abbr_index < abbr_length and abbr[abbr_index].isdigit():
30 abbr_index += 1
31 num_str = abbr[num_start_index:abbr_index]
32
33 # Leading zero or invalid number check
34 if num_str[0] == '0':
35 return False
36
37 # Move the word index forward by the number of skipped characters
38 word_index += int(num_str)
39
40 # If we've reached the end of both the word and the abbreviation, the abbreviation is valid
41 return word_index == word_length and abbr_index == abbr_length
42
1class Solution {
2 public boolean validWordAbbreviation(String word, String abbreviation) {
3 int wordLength = word.length(), abbreviationLength = abbreviation.length();
4 int wordIndex = 0, abbreviationIndex = 0;
5
6 // Iterate through the characters of the word
7 while (wordIndex < wordLength) {
8 // If the abbreviation index exceeds its length, return false
9 if (abbreviationIndex >= abbreviationLength) {
10 return false;
11 }
12 // If characters in word and abbreviation match, move to the next character
13 if (word.charAt(wordIndex) == abbreviation.charAt(abbreviationIndex)) {
14 wordIndex++;
15 abbreviationIndex++;
16 continue;
17 }
18 // If the abbreviation character is not a digit, return false
19 if (!Character.isDigit(abbreviation.charAt(abbreviationIndex))) {
20 return false;
21 }
22 int start = abbreviationIndex;
23
24 // Find the end of the digit sequence in the abbreviation
25 while (start < abbreviationLength && Character.isDigit(abbreviation.charAt(start))) {
26 ++start;
27 }
28 // Get the numerical value for the abbreviation part
29 String numString = abbreviation.substring(abbreviationIndex, start);
30 // Leading zeroes are not valid, and a substring of "0" is also invalid
31 if (abbreviationIndex == start || numString.charAt(0) == '0') {
32 return false;
33 }
34 // Convert the numbers string to the actual number
35 int skipCount = Integer.parseInt(numString);
36
37 // Move the word index forward by the numerical value
38 wordIndex += skipCount;
39
40 // Set the abbreviation index to the end of the current numerical sequence
41 abbreviationIndex = start;
42 }
43 // Ensure both word and abbreviation have been fully processed
44 return wordIndex == wordLength && abbreviationIndex == abbreviationLength;
45 }
46}
47
1class Solution {
2public:
3 bool validWordAbbreviation(string word, string abbr) {
4 int wordIndex = 0, abbrIndex = 0; // Initiate indices to iterate over word and abbreviation strings
5 int wordLength = word.size(), abbrLength = abbr.size(); // Get lengths of both word and abbreviation
6
7 // Iterate over the entire word to check if it matches with abbreviation
8 while (wordIndex < wordLength) {
9 if (abbrIndex >= abbrLength) {
10 return false; // If abbreviation is shorter than the word part processed, return false
11 }
12
13 // If the current characters match, move to the next character in both strings
14 if (word[wordIndex] == abbr[abbrIndex]) {
15 ++wordIndex;
16 ++abbrIndex;
17 continue;
18 }
19
20 // Find the next non-digit character in abbreviation to extract the numeric part
21 int numStart = abbrIndex;
22 while (numStart < abbrLength && isdigit(abbr[numStart])) {
23 ++numStart;
24 }
25
26 // Get the numeric part as a substring
27 string numStr = abbr.substr(abbrIndex, numStart - abbrIndex);
28
29 // If there's no numeric part or it starts with a zero, the abbreviation is invalid
30 if (numStart == abbrIndex || numStr[0] == '0') {
31 return false;
32 }
33
34 // Convert numeric string to integer
35 int num = stoi(numStr);
36
37 // Advance the word index by the numeric value and update the abbreviation index
38 wordIndex += num;
39 abbrIndex = numStart;
40 }
41
42 // After processing, both indices should be at the end of their respective strings
43 return wordIndex == wordLength && abbrIndex == abbrLength;
44 }
45};
46
1let wordIndex: number = 0;
2let abbrIndex: number = 0;
3let wordLength: number;
4let abbrLength: number;
5
6function isValidWordAbbreviation(word: string, abbr: string): boolean {
7 wordIndex = 0;
8 abbrIndex = 0;
9 wordLength = word.length;
10 abbrLength = abbr.length;
11
12 while (wordIndex < wordLength) {
13 if (abbrIndex >= abbrLength) {
14 return false;
15 }
16
17 if (word[wordIndex] === abbr[abbrIndex]) {
18 wordIndex++;
19 abbrIndex++;
20 continue;
21 }
22
23 let numStart = abbrIndex;
24
25 while (numStart < abbrLength && isDigit(abbr[numStart])) {
26 numStart++;
27 }
28
29 let numStr = abbr.substring(abbrIndex, numStart);
30
31 if (numStart === abbrIndex || numStr.startsWith('0')) {
32 return false;
33 }
34
35 let num = parseInt(numStr, 10);
36
37 wordIndex += num;
38 abbrIndex = numStart;
39 }
40
41 return wordIndex === wordLength && abbrIndex === abbrLength;
42}
43
44function isDigit(char: string): boolean {
45 return !isNaN(parseInt(char, 10));
46}
47
Time and Space Complexity
Time Complexity
The provided algorithm iterates over each character of the word
and abbr
strings once. On each iteration, while checking if a part of abbr
is a number, it may iterate through consecutive digits. However, each character in both strings is looked at mostly once because, after processing the digits, the index jumps from the beginning to the end of the numerical sequence.
Therefore, the time complexity of the algorithm can be represented as O(m + n)
, where m
is the length of word
and n
is the length of abbr
.
Space Complexity
The algorithm uses a constant amount of extra space for variables i
, j
, k
, t
, m
, and n
. It doesn't utilize any additional structures dependent on the input sizes.
Thus, the space complexity is O(1)
, which represents constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.