Задача: 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, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:
function generateAbbreviations($word) {
$result = [];
generateAbbreviationsHelper(str_split($word), "", 0, 0, $result);
return $result;
}

function generateAbbreviationsHelper($word, $current, $pos, $count, &$result) {
if ($pos == count($word)) {
$result[] = $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);
}

function minAbbreviation($target, $dictionary) {
$targetAbbrs = generateAbbreviations($target);
$dictAbbrs = [];
foreach ($dictionary as $word) {
$dictAbbrs = array_merge($dictAbbrs, generateAbbreviations($word));
}
$dictAbbrs = array_flip(array_flip($dictAbbrs));
$validAbbrs = array_diff($targetAbbrs, $dictAbbrs);
usort($validAbbrs, function($a, $b) { return strlen($a) - strlen($b); });
return $validAbbrs[0];
}

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