Formatted question description: https://leetcode.ca/all/527.html

527. Word Abbreviation

Level

Hard

Description

Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.

  1. Begin with the first character and then the number of characters abbreviated, which followed by the last character.
  2. If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
  3. If the abbreviation doesn’t make the word shorter, then keep it as original.

Example:

Input: [“like”, “god”, “internal”, “me”, “internet”, “interval”, “intension”, “face”, “intrusion”]

Output: [“l2e”,”god”,”internal”,”me”,”i6t”,”interval”,”inte4n”,”f2e”,”intr4n”]

Note:

  1. Both n and the length of each word will not exceed 400.
  2. The length of each word is greater than 1.
  3. The words consist of lowercase English letters only.
  4. The return answers should be in the same order as the original array.

Solution

Use a trie that stores all the words from dict. For each node in the trie, maintain a data field that stores the counts of each abbreviation.

For each word in dict, if its length does not exceed 3, then the abbreviation won’t make the word shorter, so keep it as original. Otherwise, find the shortest prefix that won’t cause any conflict, which means the abbreviation using the prefix occurs only once. Generate the abbreviation using the shortest prefix. If the abbreviation is shorter than the original word, then replace the original word with the abbreviation.

class Solution {
    TrieNode root = new TrieNode();

    public List<String> wordsAbbreviation(List<String> dict) {
        addWords(dict);
        List<String> abbreviationList = new ArrayList<String>();
        int size = dict.size();
        for (int i = 0; i < size; i++) {
            String word = dict.get(i);
            int length = word.length();
            if (length <= 3)
                abbreviationList.add(word);
            else {
                char lastLetter = word.charAt(length - 1);
                int shortestPrefixLength = searchShortestPrefix(word);
                String prefix = word.substring(0, shortestPrefixLength);
                int remainLength = length - shortestPrefixLength - 1;
                String abbreviation = prefix + remainLength + lastLetter;
                if (abbreviation.length() < length)
                    abbreviationList.add(abbreviation);
                else
                    abbreviationList.add(word);
            }
        }
        return abbreviationList;
    }

    public void addWords(List<String> dict) {
        for (String word : dict) {
            TrieNode node = root;
            int length = word.length();
            char lastLetter = word.charAt(length - 1);
            for (int i = 0; i < length; i++) {
                char letter = word.charAt(i);
                int index = letter - 'a';
                if (node.next[index] == null)
                    node.next[index] = new TrieNode();
                node = node.next[index];
                String abbreviation = String.valueOf(length - i - 2) + lastLetter;
                node.addAbbreviation(abbreviation);
            }
            node.wordEnd = true;
        }
    }

    public int searchShortestPrefix(String word) {
        TrieNode node = root;
        int length = word.length();
        char lastLetter = word.charAt(length - 1);
        int lastIndex = lastLetter - 'a';
        for (int i = 0; i < length; i++) {
            char letter = word.charAt(i);
            int index = letter - 'a';
            node = node.next[index];
            String abbreviation = String.valueOf(length - i - 2) + lastLetter;
            if (node.getAbbreviationCount(abbreviation) == 1)
                return i + 1;
        }
        return length;
    }
}

class TrieNode {
    boolean wordEnd;
    Map<String, Integer> countsMap;
    TrieNode[] next;

    public TrieNode() {
        wordEnd = false;
        countsMap = new HashMap<String, Integer>();
        next = new TrieNode[26];
    }

    public void addAbbreviation(String abbreviation) {
        int count = countsMap.getOrDefault(abbreviation, 0);
        count++;
        countsMap.put(abbreviation, count);
    }

    public int getAbbreviationCount(String abbreviation) {
        int count = countsMap.getOrDefault(abbreviation, 0);
        return count;
    }
}

All Problems

All Solutions