Practice/Meta/Leetcode 527. Word Abbreviation

Leetcode 527. Word Abbreviation

CodingMust

Problem

You are given an array of distinct words. Your task is to generate the shortest possible unique abbreviation for each word following these rules:

An abbreviation is formed by: prefix + number + last character

• The prefix is the first few characters of the word
• The number represents how many characters were omitted between the prefix and last character
• The last character is the final character of the word

Important considerations:

• An abbreviation is only valid if it's shorter than the original word (saves at least 1 character)
• If multiple words produce the same abbreviation, you must expand the prefix length for those conflicting words until all abbreviations become unique
• If no abbreviation can be shorter than the original word, keep the word as-is

Your goal is to return an array where each word is replaced with its shortest unique abbreviation.

Requirements

1. Generate abbreviations in the format: prefix + count + last character
2. Only use abbreviations that are strictly shorter than the original word
3. Resolve all conflicts by incrementally expanding the prefix length
4. Maintain the same order as the input array
5. Each abbreviation must be unique across the entire result set

Constraints

• 1 ≤ words.length ≤ 1000
• 1 ≤ words[i].length ≤ 100
• All words consist of lowercase English letters only
• All words in the input are distinct
• Time complexity should be reasonable for the given constraints
• Space complexity: O(n × m) where n is the number of words and m is average word length

Examples

Example 1:

` Input: ["like", "life", "lock", "done"] Output: ["lik1", "lif1", "loc1", "done"]

Explanation:

• "like" → Initially "l2e", conflicts with "life", expand to "li1e" (same length as original), expand to "lik1" (unique)
• "life" → Initially "l2e", conflicts with "like", expand to "li1e" (same length as original), expand to "lif1" (unique)
• "lock" → Initially "l2k", unique
• "done" → 4 letters, abbreviation "d2e" would be same length, keep as "done" `

Example 2:

` Input: ["apple", "banana", "cherry"] Output: ["a3e", "b4a", "c4y"]

Explanation: All words naturally have unique abbreviations with just the first letter as prefix. `

Example 3:

` Input: ["cat", "dog", "at"] Output: ["cat", "dog", "at"]

Explanation: All words are too short to abbreviate meaningfully. `