Java AC solution with HashMap and HashSet


  • 1
    A
    HashMap<String, HashSet<String>> abbr_map = new HashMap<String, HashSet<String>> ();
    
    public ValidWordAbbr(String[] dictionary) {
        for (String word : dictionary) {
            if (word == null || word.length() <= 2)
                continue;
            String abbr_word = getAbbrStr(word);
            if (abbr_map.containsKey(abbr_word)) {
                abbr_map.get(abbr_word).add(word);
            } else{
                HashSet<String> item = new HashSet<String> ();
                item.add(word);
                abbr_map.put(abbr_word, item);
            }
        }
    }
    
    
    public boolean isUnique(String word) {
        if (word == null || word.length() <= 2)
            return true;
        String abbr_word = getAbbrStr(word);
        if (abbr_map.containsKey(abbr_word)) {
            if (abbr_map.get(abbr_word).size() >= 2)
                return false;
            if (!abbr_map.get(abbr_word).contains(word))
                return false;
        }
        return true;
    }
    
    
    private String getAbbrStr(String s) {
        int len = s.length();
        return s.substring(0, 1) + (len - 2) + s.substring(len - 1);
    }

  • -4
    S

    ............................................


  • 0
    A

    Have you tested it before posting?
    One very obvious logic problem:
    if (!map.containsKey(abbrWord)) {
    map.put(word, abbrWord);
    }
    What's the key? abbrWord or word?


  • 0
    S

    It's a typo, the idea is using hashmap as you did, and if there's existing value, just return.

    Should be:
    if (!map.containsValue(abbrWord))

    Thanks for pointing out


  • 0
    D

    clear solution.thank you for sharing


  • 0
    S

    will your code work for case:
    dictionary = ["dog"]
    call: isUnique("dog")
    above call should return True


  • 0
    J

    Our answers are exactly the same except I used ArrayList instead of your HashSet.


  • 0
    A

    pay a attention to the time complexity of using ArrayList.


Log in to reply
 

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