LeetCode 527: Word Abbreviation Solution

Master LeetCode problem 527 (Word Abbreviation), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

527. Word Abbreviation

Hard

Array String Greedy Trie Sorting

Problem Explanation

Explanation

To solve this problem, we need to find the minimum abbreviation of each word in the given list of words. We can approach this problem by generating all possible abbreviations for each word and then checking if the abbreviation is unique or not among all the words. If it is unique, then we can use that abbreviation; otherwise, we need to generate a longer abbreviation.

We can use the backtracking technique to generate all possible abbreviations for a word. At each step, we can either choose to abbreviate the current character or keep it as it is. We need to keep track of the current abbreviation, the number of consecutive abbreviated characters, and the index of the current character in the word.

After generating all possible abbreviations for a word, we can check if the abbreviation is unique among all the words. If it is unique, we can use it; otherwise, we need to generate a longer abbreviation and repeat the process.

The time complexity of this approach is exponential, as we are generating all possible abbreviations for each word. The space complexity is also exponential due to the recursive calls.

Solution Code

import java.util.*;

class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : dict) {
            String abbr = getAbbreviation(word, 1);
            if (!map.containsKey(abbr)) {
                map.put(abbr, new ArrayList<>());
            }
            map.get(abbr).add(word);
        }
        
        List<String> res = new ArrayList<>();
        for (String word : dict) {
            int prefix = 1;
            String abbr = getAbbreviation(word, prefix);
            List<String> group = map.get(abbr);
            while (group.size() > 1 && prefix < word.length()) {
                prefix++;
                abbr = getAbbreviation(word, prefix);
                group = map.get(abbr);
            }
            res.add(abbr);
        }
        
        return res;
    }
    
    private String getAbbreviation(String word, int prefix) {
        if (prefix >= word.length() - 2) {
            return word;
        }
        return word.substring(0, prefix) + (word.length() - prefix - 1) + word.charAt(word.length() - 1);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 527 (Word Abbreviation)?

This page provides optimized solutions for LeetCode problem 527 (Word Abbreviation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 527 (Word Abbreviation)?

The time complexity for LeetCode 527 (Word Abbreviation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 527 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 527 in Java, C++, or Python.

Back to LeetCode Solutions