Practice/Meta/Leetcode 408. Valid Word Abbreviation

Leetcode 408. Valid Word Abbreviation

CodingMust

Problem

You are given a word and an abbreviation string. Your task is to determine whether the abbreviation is a valid representation of the word.

An abbreviation is formed by replacing sequences of characters in the original word with numbers that represent how many characters were replaced. For example, "internationalization" can be abbreviated as "i18n" (the letter 'i', followed by 18 characters, followed by 'n').

The abbreviation string may contain:

• Letters that must match the corresponding letter in the word at the current position
• Numbers that indicate how many characters to skip in the word

An abbreviation is valid if following its instructions (matching letters and skipping the specified number of characters) produces exactly the original word.

Requirements

1. Numbers in the abbreviation represent the count of characters to skip
2. Letters in the abbreviation must match exactly with the word at the current position
3. Numbers cannot have leading zeros (e.g., "01", "007" are invalid)
4. The abbreviation must account for exactly all characters in the word - no more, no less
5. Return true if the abbreviation is valid, false otherwise

Constraints

• 1 ≤ word.length ≤ 20
• 1 ≤ abbr.length ≤ 10
• word consists of only lowercase English letters
• abbr consists of lowercase English letters and digits
• Time complexity: O(n) where n is the length of the abbreviation
• Space complexity: O(1)

Examples

Example 1:

` Input: word = "internationalization", abbr = "i12iz4n" Output: true Explanation:

• 'i' matches the first character
• Skip 12 characters: "nternational"
• 'i' matches character at position 13
• 'z' matches character at position 14
• Skip 4 characters: "atio"
• 'n' matches the last character `

Example 2:

` Input: word = "apple", abbr = "a2e" Output: false Explanation:

• 'a' matches the first character
• Skip 2 characters: "pp"
• We're now at position 3 (character 'l'), but abbr expects 'e'
• This doesn't match, so it's invalid `

Example 3:

Input: word = "substitution", abbr = "s010n" Output: false Explanation: Numbers with leading zeros are not allowed in valid abbreviations.

Example 4:

Input: word = "word", abbr = "4" Output: false Explanation: The abbreviation would skip 4 characters, but there are no letters to match. The entire word cannot be just a number without boundary letters.