288. Unique Word Abbreviation 🔒

Description

The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.

For example:

• dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.
• internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
• it --> it because any word with only two characters is an abbreviation of itself.

Implement the ValidWordAbbr class:

• ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
• boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):
  • There is no word in dictionary whose abbreviation is equal to word's abbreviation.
  • For any word in dictionary whose abbreviation is equal to word's abbreviation, that word and word are the same.

 

Example 1:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

 

Constraints:

• 1 <= dictionary.length <= 3 * 104
• 1 <= dictionary[i].length <= 20
• dictionary[i] consists of lowercase English letters.
• 1 <= word.length <= 20
• word consists of lowercase English letters.
• At most 5000 calls will be made to isUnique.

Solutions

Solution 1: Hash Table

According to the problem description, we define a function \(abbr(s)\), which calculates the abbreviation of the word \(s\). If the length of the word \(s\) is less than \(3\), then its abbreviation is itself; otherwise, its abbreviation is its first letter + (its length - 2) + its last letter.

Next, we define a hash table \(d\), where the key is the abbreviation of the word, and the value is a set, the elements of which are all words abbreviated as that key. We traverse the given word dictionary, and for each word \(s\) in the dictionary, we calculate its abbreviation \(abbr(s)\), and add \(s\) to \(d[abbr(s)]\).

When judging whether the word \(word\) meets the requirements of the problem, we calculate its abbreviation \(abbr(word)\). If \(abbr(word)\) is not in the hash table \(d\), then \(word\) meets the requirements of the problem; otherwise, we judge whether there is only one element in \(d[abbr(word)]\). If there is only one element in \(d[abbr(word)]\) and that element is \(word\), then \(word\) meets the requirements of the problem.

In terms of time complexity, the time complexity of initializing the hash table is \(O(n)\), where \(n\) is the length of the word dictionary; the time complexity of judging whether a word meets the requirements of the problem is \(O(1)\). In terms of space complexity, the space complexity of the hash table is \(O(n)\).

Python3JavaC++GoTypeScript

class ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.d = defaultdict(set)
        for s in dictionary:
            self.d[self.abbr(s)].add(s)

    def isUnique(self, word: str) -> bool:
        s = self.abbr(word)
        return s not in self.d or all(word == t for t in self.d[s])

    def abbr(self, s: str) -> str:
        return s if len(s) < 3 else s[0] + str(len(s) - 2) + s[-1]


# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)

class ValidWordAbbr {
    private Map<String, Set<String>> d = new HashMap<>();

    public ValidWordAbbr(String[] dictionary) {
        for (var s : dictionary) {
            d.computeIfAbsent(abbr(s), k -> new HashSet<>()).add(s);
        }
    }

    public boolean isUnique(String word) {
        var ws = d.get(abbr(word));
        return ws == null || (ws.size() == 1 && ws.contains(word));
    }

    private String abbr(String s) {
        int n = s.length();
        return n < 3 ? s : s.substring(0, 1) + (n - 2) + s.substring(n - 1);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string>& dictionary) {
        for (auto& s : dictionary) {
            d[abbr(s)].insert(s);
        }
    }

    bool isUnique(string word) {
        string s = abbr(word);
        return !d.count(s) || (d[s].size() == 1 && d[s].count(word));
    }

private:
    unordered_map<string, unordered_set<string>> d;

    string abbr(string& s) {
        int n = s.size();
        return n < 3 ? s : s.substr(0, 1) + to_string(n - 2) + s.substr(n - 1, 1);
    }
};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
 * bool param_1 = obj->isUnique(word);
 */

type ValidWordAbbr struct {
    d map[string]map[string]bool
}

func Constructor(dictionary []string) ValidWordAbbr {
    d := make(map[string]map[string]bool)
    for _, s := range dictionary {
        abbr := abbr(s)
        if _, ok := d[abbr]; !ok {
            d[abbr] = make(map[string]bool)
        }
        d[abbr][s] = true
    }
    return ValidWordAbbr{d}
}

func (this *ValidWordAbbr) IsUnique(word string) bool {
    ws := this.d[abbr(word)]
    return ws == nil || (len(ws) == 1 && ws[word])
}

func abbr(s string) string {
    n := len(s)
    if n < 3 {
        return s
    }
    return fmt.Sprintf("%c%d%c", s[0], n-2, s[n-1])
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * obj := Constructor(dictionary);
 * param_1 := obj.IsUnique(word);
 */

class ValidWordAbbr {
    private d: Map<string, Set<string>> = new Map();

    constructor(dictionary: string[]) {
        for (const s of dictionary) {
            const abbr = this.abbr(s);
            if (!this.d.has(abbr)) {
                this.d.set(abbr, new Set());
            }
            this.d.get(abbr)!.add(s);
        }
    }

    isUnique(word: string): boolean {
        const ws = this.d.get(this.abbr(word));
        return ws === undefined || (ws.size === 1 && ws.has(word));
    }

    abbr(s: string): string {
        const n = s.length;
        return n < 3 ? s : s[0] + (n - 2) + s[n - 1];
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * var obj = new ValidWordAbbr(dictionary)
 * var param_1 = obj.isUnique(word)
 */

Comments