Verbose Java Solution, HashMap(s)


  • 7

    It's 10:30 PM now. Try to add some comments in-line. Will add more explanation later...

    public class Solution {
        public List<String> wordsAbbreviation(List<String> dict) {
            Map<String, String> wordToAbbr = new HashMap<>();
            Map<Integer, List<String>> groups = new HashMap<>();
            
            // Try to group words by their length. Because no point to compare words with different length.
            // Also no point to look at words with length < 4.
            for (String word : dict) {
                int len = word.length();
                if (len < 4) {
                    wordToAbbr.put(word, word);
                }
                else {
                    List<String> g = groups.getOrDefault(len, new ArrayList<String>());
                    g.add(word);
                    groups.put(len, g);
                }
            }
            
            // For each group of words with same length, generate a result HashMap.
            for (int len : groups.keySet()) {
                Map<String, String> res = getAbbr(groups.get(len));
                for (String word : res.keySet()) {
                    wordToAbbr.put(word, res.get(word));
                }
            }
            
            // Generate the result list
            List<String> result = new ArrayList<>();
            for (String word : dict) {
                result.add(wordToAbbr.get(word));
            }
            
            return result;
        }
        
        private Map<String, String> getAbbr(List<String> words) {
            Map<String, String> res = new HashMap<>();
            int len = words.get(0).length();
            
            // Try to abbreviate a word from index 1 to len - 2 
            for (int i = 1; i < len - 2; i++) {
                Map<String, String> abbrToWord = new HashMap<>();
                for (String s : words) {
                    if (res.containsKey(s)) continue;
                    // Generate the current abbreviation
                    String abbr = s.substring(0, i) + (len - 1 - i) + s.charAt(len - 1);
                    // Tick: use reversed abbreviation to word map to check if there is any duplicated abbreviation
                    if (!abbrToWord.containsKey(abbr)) {
                        abbrToWord.put(abbr, s);
                    }
                    else {
                        abbrToWord.put(abbr, "");
                    }
                }
    
                // Add unique abbreviations find during this round to result HashMap
                for (String abbr : abbrToWord.keySet()) {
                    String s = abbrToWord.get(abbr);
                    // Not a unique abbreviation
                    if (s.length() == 0) continue;
                    res.put(s, abbr);
                }
            }
            
            // Add all words that can't be shortened.
            for (String s : words) {
                if (!res.containsKey(s)) {
                    res.put(s, s);
                }
            }
            
            return res;
        }
    }
    

  • 0

    @shawngao
    Well... I do not even have time to have a look at the last one. Super tired now.
    Good job!


  • 0
    A

    Good solution! however I am still wondering if that can be solved with Trie Tree :)
    anybody's help will be appreciated.


  • 0
    L

    @AdrianFeng
    here is my solution with Trie. However it got Memory Limit Exceed.

    class Solution {
    	struct TrieNode {
    		int count;
    		vector<TrieNode *> children;
    		TrieNode(int x) : count(x), children(26, nullptr) {}
    	};
    	void insert(TrieNode *cur, string &s, int i)
    	{
    		if (i == s.length()) {
    			return;
    		}
    		if (!cur->children[s[i] - 'a']) {
    			cur->children[s[i] - 'a'] = new TrieNode(1);
    		}
    		else {
    			cur->children[s[i] - 'a']->count += 1;
    		}
    		insert(cur->children[s[i] - 'a'], s, i + 1);
    	}
    	int search(TrieNode *cur, string &s, int i) {
    		if (i + 3 >= s.length()) {
    			return -1;
    		}
    		if (cur->children[s[i] - 'a']->count == 1) {
    			return i + 1;
    		}
    		else {
    			return search(cur->children[s[i] - 'a'], s, i + 1);
    		}
    	}
    public:
    	vector<string> wordsAbbreviation(vector<string>& dict) {
    		vector<vector<TrieNode *>> dir(401, vector<TrieNode *>(26, nullptr));
    		vector<string> ans(dict.size());
    		for (int i = 0; i < dict.size(); ++i) {
    			string &word = dict[i];
    			if (!dir[word.length()][*word.rbegin() - 'a']) {
    				dir[word.length()][*word.rbegin() - 'a'] = new TrieNode(0);
    			}
    			insert(dir[word.length()][*word.rbegin() - 'a'], word, 0);
    		}
    		int index = 0;
    		for (int i = 0; i < dict.size(); ++i) {
    			string &word = dict[i];
    			int pos = search(dir[word.length()][*word.rbegin() - 'a'], word, 0);
    			if (pos == -1) {
    				ans[index++] = word;
    			}
    			else {
    				ans[index++] = word.substr(0, pos) + to_string(word.length() - pos - 1) + word.substr(word.length() - 1, 1);
    			}
    		}
    		return ans;
    	}
    };
    

  • 1

    @AdrianFeng I thought about Trie at the beginning. But the abbreviation must contain the last letter. It makes the problem difficult by using Trie (Prefix Tree). Then I gave it up.


  • 0
    L

    @shawngao This can be solved by generate different Tries for words with different lengths and different last character.


  • 0
    L

    @shawngao The main problem for Trie is it costs too much space if all the words are long and are different from each other.


  • 1

    @leeylf I also use a trie for different abbreviations, but TLE at the last test case. It indeed costs a lot of time to construct the trie and search the trie.


  • 0
    W

    I wrote a shorter version using Java 8 features.

      public List<String> wordsAbbreviation(List<String> dict) {
        List<String> result = new ArrayList<>();
        Map<String, String> map = new HashMap<>(); // key is word, value is abbreviation
        Map<Integer, List<String>> lengthMap = new HashMap<>(); // key is length, value is words
        for (String word : dict)
          if (word.length() < 4) map.put(word, word);
          else lengthMap.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
        lengthMap.values().forEach(words -> map.putAll(getAbbreviation(words)));
        dict.forEach(word -> result.add(map.get(word)));
        return result;
      }
    
      private Map<String, String> getAbbreviation(List<String> words) {
        Map<String, String> result = new HashMap<>();
        Set<String> next = new HashSet<>(words);
        for (int i = 1, len = words.get(0).length(), end = len - 2; i < end && !next.isEmpty(); i++) {
          Map<String, String> map = new HashMap<>(); // key is abbreviation, value is word
          for (String s : next)
            map.compute(getAbbreviation(s, i), (k, v) -> v == null ? s : "");
          for (Entry<String, String> e : map.entrySet())
            if (e.getValue().length() > 0) {
              next.remove(e.getValue());
              result.put(e.getValue(), e.getKey());
            }
        }
        next.forEach(word -> result.put(word, word));
        return result;
      }
    
      private String getAbbreviation(String s, int firstPartEnd) {
        return s.substring(0, firstPartEnd) + (s.length() - 1 - firstPartEnd) + s.charAt(s.length() - 1);
      }

  • 0

    @shawngao

       HashMap<Integer,TireTree>[] arr = (HashMap<Integer,TireTree>[])new HashMap[26];
    

    arr[] used to store the last character. The key of the hashmap is the length of the string, the value is the tire tree you created.


  • 0
    K

    @shawngao
    Below is Trie solution passed test cases
    public class WordAbbreviation {
    class Node{
    int[] count;
    Node[] children;
    Node(){
    children = new Node[26];
    count = new int[26];
    }
    }
    public int searchWord(Node root,String word){
    Node x = root;
    int index = 0;
    for(int i=0;i<word.length();i++,index++){
    char c = word.charAt(i);
    if(x.children[c-'a']==null||x.count[c-'a']==0)return index;
    x = x.children[c-'a'];
    }
    return -1;
    }
    public void insertWord(Node root,String word){
    Node x = root;
    for(int i=0;i<word.length();i++){
    char c = word.charAt(i);
    if(x.children[c-'a']==null)x.children[c-'a'] = new Node();
    else x.count[c-'a']++;
    x = x.children[c-'a'];
    }
    }
    public List<String> wordsAbbreviation(List<String> dict) {
    Map<String,List<Integer>> map = new HashMap<>();
    for(int i=0;i<dict.size();i++){
    if(dict.get(i).length()>=4){
    String abb = getAbbreviation(dict.get(i));
    if(!map.containsKey(abb))map.put(abb,new ArrayList<Integer>());
    map.get(abb).add(i);
    }
    }
    for(Map.Entry<String,List<Integer>> en : map.entrySet()){
    if(en.getValue().size()==1){
    dict.set(en.getValue().get(0),getAbbreviation(dict.get(en.getValue().get(0))));
    }else{
    findAbbreviation(dict,en.getValue());
    }
    }
    return dict;
    }
    public void findAbbreviation(List<String> dict,List<Integer> dup){
    Node root = new Node();
    for(int i : dup){
    insertWord(root,dict.get(i));
    }
    for(int i : dup){
    String word = dict.get(i);
    int pos = searchWord(root,word);
    if(pos>=word.length()-3){
    dict.set(i,word);
    }else{
    dict.set(i,word.substring(0,pos+1)+(word.length()-(pos+2))+word.substring(word.length()-1));
    }
    }
    }
    public String getAbbreviation(String word){
    return word.charAt(0)+""+(word.length()-2)+""+word.charAt(word.length()-1);
    }
    }


Log in to reply
 

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