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

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

1⃣Инициализация и создание начальных сокращений:
Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.

2⃣Обработка коллизий:
Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями.
Если сокращение не уникально, увеличьте длину префикса и повторите проверку.

3⃣Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

class Solution {
    /**
     * @param String[] $words
     * @return String[]
     */
    function wordsAbbreviation($words) {
        $n = count($words);
        $ans = array_fill(0, $n, "");
        $prefix = array_fill(0, $n, 0);

        for ($i = 0; $i < $n; ++$i) {
            $ans[$i] = $this->abbrev($words[$i], 0);
        }

        for ($i = 0; $i < $n; ++$i) {
            while (true) {
                $dupes = [];
                for ($j = $i + 1; $j < $n; ++$j) {
                    if ($ans[$i] == $ans[$j]) {
                        $dupes[] = $j;
                    }
                }

                if (empty($dupes)) break;
                $dupes[] = $i;
                foreach ($dupes as $k) {
                    $ans[$k] = $this->abbrev($words[$k], ++$prefix[$k]);
                }
            }
        }

        return $ans;
    }

    function abbrev($word, $i) {
        $n = strlen($word);
        if ($n - $i <= 3) return $word;
        return substr($word, 0, $i + 1) . ($n - $i - 2) . substr($word, -1);
    }
}

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