🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium
Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].
Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.
Пример:
Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
👨💻 Алгоритм:
1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки.
2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк.
3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.
😎 Решение:
fun numSpecialEquivGroups(words: Array): Int {
val uniqueForms = mutableSetOf()
for (word in words) {
val evenChars = word.filterIndexed { index, _ -> index % 2 == 0 }.toCharArray().sorted()
val oddChars = word.filterIndexed { index, _ -> index % 2 != 0 }.toCharArray().sorted()
val canonicalForm = evenChars.joinToString("") + oddChars.joinToString("")
uniqueForms.add(canonicalForm)
}
return uniqueForms.size
Ставь 👍 и забирай 📚 Базу знаний
