Задача: 411. Minimum Unique Word Abbreviation
Сложность: hard

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.

Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

👨‍💻 Алгоритм:

1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        Set<String> targetAbbrs = generateAbbreviations(target);
        Set<String> dictAbbrs = new HashSet<>();
        for (String word : dictionary) {
            dictAbbrs.addAll(generateAbbreviations(word));
        }
        targetAbbrs.removeAll(dictAbbrs);
        return targetAbbrs.stream().min((a, b) -> Integer.compare(a.length(), b.length())).orElse("");
    }

    private Set<String> generateAbbreviations(String word) {
        Set<String> result = new HashSet<>();
        generateAbbreviationsHelper(word.toCharArray(), "", 0, 0, result);
        return result;
    }

    private void generateAbbreviationsHelper(char[] word, String current, int pos, int count, Set<String> result) {
        if (pos == word.length) {
            result.add(current + (count > 0 ? count : ""));
            return;
        }
        generateAbbreviationsHelper(word, current, pos + 1, count + 1, result);
        generateAbbreviationsHelper(word, current + (count > 0 ? count : "") + word[pos], pos + 1, 0, result);
    }
}

Ставь 👍 и забирай 📚 Базу знаний