Java Accepted Solution Using HashMap, List and Trie


  • 0
    A
    class Solution {
        private static class Trie {
    
            private static class TrieNode {
                private Map<Character, TrieNode> charNodeMap = new HashMap<>();
                private int wordCount = 0;
            }
    
            private TrieNode root = new TrieNode();
    
            public void addWord(final String word) {
                TrieNode current = root;
                for (char c : word.toCharArray()) {
                    current.wordCount++;
                    if (!current.charNodeMap.containsKey(c)) {
                        current.charNodeMap.put(c, new TrieNode());
                    }
                    current = current.charNodeMap.get(c);
                }
                current.wordCount++;
            }
    
            public String findUniquePrefix(final String word) {
                TrieNode current = root;
                StringBuffer buffer = new StringBuffer();
                for (char c : word.toCharArray()) {
                    if (current.wordCount == 1) {
                        break;
                    } else {
                        buffer.append(c);
                        current = current.charNodeMap.get(c);
                    }
                }
                return buffer.toString();
            }
        }
    
        public List<String> wordsAbbreviation(final List<String> dictionary) {
            Map<String, List<String>> abbreviations = new HashMap<>();
            Map<String, Integer> wordIndexMap = new HashMap<>();
    
            for (int i = 0; i < dictionary.size(); i++) {
                String word = dictionary.get(i);
                String abbreviation = word.length() <= 3 ? word : "" + word.charAt(0) + (word.length() - 2) + word.charAt(word.length()-1);
    
                if (!abbreviations.containsKey(abbreviation)) {
                    abbreviations.put(abbreviation, new ArrayList<>());
                }
                List<String> words = abbreviations.get(abbreviation);
                words.add(word);
                wordIndexMap.put(word, i);
            }
    
            Map<String, String> newAbbreviations = new HashMap<>();
            final Iterator<Map.Entry<String, List<String>>> entryIterator = abbreviations.entrySet().iterator();
            while (entryIterator.hasNext()) {
                Map.Entry<String, List<String>> entry = entryIterator.next();
                List<String> words = entry.getValue();
                if (words.size() == 1) {
                    continue;
                }
    
                entryIterator.remove();
    
                Trie trie = new Trie();
                for (String word : words) {
                    trie.addWord(word);
                }
    
                for (String word : words) {
                    String uniquePrefix = trie.findUniquePrefix(word);
                    final int numDigits = word.length() - uniquePrefix.length() - 1;
                    String abbreviation = numDigits > 1 ? uniquePrefix + numDigits + word.charAt(word.length()-1) : word;
                    newAbbreviations.put(abbreviation, word);
                }
            }
    
            List<String> result = new ArrayList<>(Collections.nCopies(dictionary.size(), null));
            for (String abbreviation : abbreviations.keySet()) {
                String word = abbreviations.get(abbreviation).iterator().next();
                result.set(wordIndexMap.get(word), abbreviation);
            }
    
            for (String abbreviation : newAbbreviations.keySet()) {
                String word = newAbbreviations.get(abbreviation);
                result.set(wordIndexMap.get(word), abbreviation);
            }
    
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.