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 <= 20word consists of only lowercase English letters.1 <= abbr.length <= 10abbr consists of lowercase English letters and digits.abbr will fit in a 32-bit integer.Problem Overview: Given a word and its abbreviation, determine whether the abbreviation correctly represents the original word. Numbers in the abbreviation represent how many characters are skipped in the word, while letters must match exactly in order.
Approach 1: Expand Abbreviation (String Simulation) (Time: O(n), Space: O(n))
The most straightforward method builds the expanded string represented by the abbreviation. Iterate through the abbreviation: if the current character is a digit, parse the full number and append that many placeholder characters (or skip count tracking). If it is a letter, append it directly. After expansion, compare the constructed string with the original word character by character. This approach is easy to reason about but wastes memory because the expanded string can be as long as the original word. It also performs unnecessary string construction when the goal is only validation.
Approach 2: Two Pointers Simulation (Time: O(n), Space: O(1))
The optimal solution processes both strings in a single pass using two indices. One pointer walks through the word and another through the abbreviation. When the abbreviation contains a letter, it must match the current character in the word, and both pointers move forward. When the abbreviation contains a digit, parse the entire number and advance the word pointer by that amount. Leading zeros are invalid and must be rejected immediately. This approach works because the abbreviation directly encodes how far the pointer should jump in the word. The algorithm only scans each character once and never constructs intermediate strings.
Using two pointers keeps the implementation simple and avoids extra memory allocation. The logic mainly revolves around parsing digits and synchronizing movement between the two indices. Since each character of the abbreviation and word is processed at most once, the runtime remains linear.
Handling numeric parsing correctly is the key detail. When a digit is encountered, repeatedly multiply the current value by 10 and add the new digit until a non-digit appears. This handles multi-digit abbreviations like 12 correctly. After parsing, move the word pointer forward by the parsed number.
The solution is essentially a string parsing simulation problem using techniques common in string processing tasks. Careful boundary checks ensure the pointer never moves beyond the word length.
Recommended for interviews: Interviewers expect the two-pointer simulation. The brute-force expansion approach demonstrates understanding of the abbreviation format, but the O(1) space pointer method shows stronger problem-solving and attention to efficiency. Most candidates who pass interviews implement the linear scan with digit parsing.
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).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Expand Abbreviation (String Simulation) | O(n) | O(n) | Good for understanding the abbreviation format or quick prototyping |
| Two Pointers Simulation | O(n) | O(1) | Optimal solution for interviews and production code |
VALID WORD ABBREVIATION | LEETCODE # 408 | PYTHON TWO POINTERS SOLUTION • Cracking FAANG • 16,668 views views
Watch 9 more video solutions →Practice Valid Word Abbreviation with our built-in code editor and test cases.
Practice on FleetCode