Сложность: medium
Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.
Пример:
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.
👨💻 Алгоритм:
1⃣Инициализация:
Создайте словарь сокращений abbrDict, который будет хранить сокращения слов в виде ключей и булевы значения, указывающие, уникально ли сокращение. Создайте множество dict, содержащее все слова из словаря, чтобы быстро проверять наличие слова в словаре.
2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение. Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).
3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict. Если сокращение отсутствует в abbrDict, возвращайте true. Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.
😎 Решение:
class ValidWordAbbr:
def __init__(self, dictionary: List[str]):
self.abbr_dict = {}
self.dict = set(dictionary)
for word in self.dict:
abbr = self.to_abbr(word)
self.abbr_dict[abbr] = not self.abbr_dict.get(abbr, False)
def isUnique(self, word: str) -> bool:
abbr = self.to_abbr(word)
has_abbr = self.abbr_dict.get(abbr)
return has_abbr is None or (has_abbr and word in self.dict)
def to_abbr(self, word: str) -> str:
n = len(word)
if n <= 2:
return word
return f"{word[0]}{n - 2}{word[-1]}"
Ставь 👍 и забирай 📚 Базу знаний