Задача: 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⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

public class Solution {
    public IList<string> WordsAbbreviation(IList<string> words) {
        int n = words.Count;
        string[] ans = new string[n];
        int[] prefix = new int[n];

        for (int i = 0; i < n; ++i)
            ans[i] = Abbrev(words[i], 0);

        for (int i = 0; i < n; ++i) {
            while (true) {
                HashSet<int> dupes = new HashSet<int>();
                for (int j = i + 1; j < n; ++j) {
                    if (ans[i] == ans[j])
                        dupes.Add(j);
                }

                if (dupes.Count == 0) break;
                dupes.Add(i);
                foreach (int k in dupes)
                    ans[k] = Abbrev(words[k], ++prefix[k]);
            }
        }

        return ans.ToList();
    }

    private string Abbrev(string word, int i) {
        int n = word.Length;
        if (n - i <= 3) return word;
        return word.Substring(0, i + 1) + (n - i - 2) + word[n - 1];
    }
}

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