java solution using trie


  • 0
    2
    public class Solution {
        public List<String> wordsAbbreviation(List<String> dict) {
            HashMap<Integer, Node> map = new HashMap<Integer, Node>();
            for (String s : dict) {
                if (s.length() > 3) {
                    if (!map.containsKey(s.length())) {
                        map.put(s.length(), new Node());
                    }
                    add(map.get(s.length()), rightShift(s));
                }
            }
            List<String> ret = new ArrayList<String>();
            for (String s : dict) {
                if (s.length() > 3) {
                    int numAbbr = s.length() - minUniquePrefix(map.get(s.length()), rightShift(s));
                    numAbbr = Math.min(numAbbr, s.length() - 2);
                    if (numAbbr > 1) {
                        ret.add(leftShift(rightShift(s).substring(0, s.length() - numAbbr) + numAbbr));
                    }
                    else {
                        ret.add(s);
                    }
                }
                else {
                    ret.add(s);
                }
            }
            return ret;
        }
        
        private String leftShift(String s) {
            return s.substring(1) + s.substring(0, 1);
        }
        
        private String rightShift(String s) {
            return s.substring(s.length() - 1) + s.substring(0, s.length() - 1);
        }
        
        private int minUniquePrefix(Node root, String s) {
            for (int i = 0; i < s.length(); i++) {
                root = root.child[s.charAt(i) - 'a'];
                if (root.count == 1) {
                    return i + 1;
                }
            }
            return s.length();
        }
        
        private void add(Node root, String s) {
            for (int i = 0; i < s.length(); i++) {
                int j = s.charAt(i) - 'a';
                if (root.child[j] == null) {
                    root.child[j] = new Node();
                }
                root = root.child[j];
                root.count++;
            }
        }
        
        private class Node {
            int count = 0;
            Node[] child = new Node[26];
        }
    }
    

Log in to reply
 

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