RUST GYM v0.2.8

288. Unique Word Abbreviation

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"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"]]
Output
[null, false, true, false, 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.

Rust Solution

use std::collections::hash_map::DefaultHasher;
use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::Hasher;

struct ValidWordAbbr {
    abbr: HashMap<u64, HashSet<String>>,
}

impl ValidWordAbbr {
    fn new(dictionary: Vec<String>) -> Self {
        let mut abbr: HashMap<u64, HashSet<String>> = HashMap::new();
        for s in dictionary {
            let hash = Self::abbr_hash(&s);
            abbr.entry(hash).or_default().insert(s);
        }
        ValidWordAbbr { abbr }
    }

    fn abbr_hash(s: &str) -> u64 {
        let s: Vec<u8> = s.bytes().collect();
        let n = s.len();
        let mut hasher = DefaultHasher::new();
        if !s.is_empty() {
            hasher.write_u8(s[0]);
            hasher.write_usize(s.len());
            hasher.write_u8(s[n - 1]);
            hasher.finish()
        } else {
            0
        }
    }

    fn is_unique(&self, word: String) -> bool {
        let hash = Self::abbr_hash(&word);
        if let Some(set) = self.abbr.get(&hash) {
            set.contains(&word) && set.len() == 1
        } else {
            true
        }
    }
}

#[test]
fn test() {
    let obj = ValidWordAbbr::new(vec_string!["deer", "door", "cake", "card"]);
    assert_eq!(obj.is_unique("dear".to_string()), false);
    assert_eq!(obj.is_unique("cart".to_string()), true);
    assert_eq!(obj.is_unique("cane".to_string()), false);
    assert_eq!(obj.is_unique("make".to_string()), true);
    assert_eq!(obj.is_unique("door".to_string()), false);
}

Having problems with this solution? Click here to submit an issue on github.