527. Word Abbreviation

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.

View Leetcode Problem

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);
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution