Summary

This problem has a low acceptance rate for a reason. The logic in isUnique can be a little tricky to get right due to the number of cases you need to consider. We highly recommend that you practice this similar but easier problem first - Two Sum III - Data structure design.

Solution

Approach #1 (Brute Force)

Let us begin by storing the dictionary first in the constructor. To determine if a word\'s abbreviation is unique with respect to a word in the dictionary, we check if all the following conditions are met:

\n
1. They are not the same word.
\n
2. They both have equal lengths.
\n
3. They both share the same first and last letter.
\n

Note that Condition #1 is implicit because from the problem statement:

\n

A word\'s abbreviation is unique if no other word from the dictionary has the same abbreviation.

\n

public class ValidWordAbbr {\n    private final String[] dict;\n\n    public ValidWordAbbr(String[] dictionary) {\n        dict = dictionary;\n    }\n\n    public boolean isUnique(String word) {\n        int n = word.length();\n        for (String s : dict) {\n            if (word.equals(s)) {\n                continue;\n            }\n            int m = s.length();\n            if (m == n\n                && s.charAt(0) == word.charAt(0)\n                && s.charAt(m - 1) == word.charAt(n - 1)) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n

Complexity analysis

\n
• Time complexity : $$O(n)$$ for each isUnique call.\nAssume that $$n$$ is the number of words in the dictionary, each isUnique call takes $$O(n)$$ time.
\n

Approach #2 (Hash Table) [Accepted]

Note that isUnique is called repeatedly for the same set of words in the dictionary each time. We should pre-process the dictionary to speed it up.

Ideally, a hash table supports constant time look up. What should the key-value pair be?

Well, the idea is to group the words that fall under the same abbreviation together. For the value, we use a Set instead of a List to guarantee uniqueness.

The logic in isUnique(word) is tricky. You need to consider the following cases:

\n
1. Does the word\'s abbreviation exists in the dictionary? If not, then it must be unique.
\n
2. If above is yes, then it can only be unique if the grouping of the abbreviation contains no other words except word.
\n

public class ValidWordAbbr {\n    private final Map<String, Set<String>> abbrDict = new HashMap<>();\n\n    public ValidWordAbbr(String[] dictionary) {\n        for (String s : dictionary) {\n            String abbr = toAbbr(s);\n            Set<String> words = abbrDict.containsKey(abbr)\n                ? abbrDict.get(abbr) : new HashSet<>();\n            words.add(s);\n            abbrDict.put(abbr, words);\n        }\n    }\n\n    public boolean isUnique(String word) {\n        String abbr = toAbbr(word);\n        Set<String> words = abbrDict.get(abbr);\n        return words == null || (words.size() == 1 && words.contains(word));\n    }\n\n    private String toAbbr(String s) {\n        int n = s.length();\n        if (n <= 2) {\n            return s;\n        }\n        return s.charAt(0) + Integer.toString(n - 2) + s.charAt(n - 1);\n    }\n}\n

Approach #3 (Hash Table) [Accepted]

Let us consider another approach using a counter as the table\'s value. For example, assume the dictionary = ["door", "deer"], we have the mapping of {"d2r" -> 2}. However, this mapping alone is not enough, because we need to consider whether the word exists in the dictionary. This can be easily overcome by inserting the entire dictionary into a set.

When an abbreviation\'s counter exceeds one, we know this abbreviation must not be unique because at least two different words share the same abbreviation. Therefore, we can further simplify the counter to just a boolean.

public class ValidWordAbbr {\n    private final Map<String, Boolean> abbrDict = new HashMap<>();\n    private final Set<String> dict;\n\n    public ValidWordAbbr(String[] dictionary) {\n        dict = new HashSet<>(Arrays.asList(dictionary));\n        for (String s : dict) {\n            String abbr = toAbbr(s);\n            abbrDict.put(abbr, !abbrDict.containsKey(abbr));\n        }\n    }\n\n    public boolean isUnique(String word) {\n        String abbr = toAbbr(word);\n        Boolean hasAbbr = abbrDict.get(abbr);\n        return hasAbbr == null || (hasAbbr && dict.contains(word));\n    }\n\n    private String toAbbr(String s) {\n        int n = s.length();\n        if (n <= 2) {\n            return s;\n        }\n        return s.charAt(0) + Integer.toString(n - 2) + s.charAt(n - 1);\n    }\n}\n

Complexity analysis

\n
• \n

  Time complexity : $$O(n)$$ pre-processing, $$O(1)$$ for each isUnique call.\nBoth Approach #2 and Approach #3 above take $$O(n)$$ pre-processing time in the constructor. This is totally worth it if isUnique is called repeatedly.

  \n
\n
• \n

  Space complexity : $$O(n)$$ .\nWe traded the extra $$O(n)$$ space storing the table to reduce the time complexity in isUnique.

  \n
\n