Сложность: 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⃣Размер множества будет равен количеству групп специально-эквивалентных строк.
😎 Решение:
func numSpecialEquivGroups(_ words: [String]) -> Int {
var uniqueForms = Set<String>()
for word in words {
let evenChars = String(word.enumerated().filter { $0.offset % 2 == 0 }.map { $0.element }.sorted())
let oddChars = String(word.enumerated().filter { $0.offset % 2 != 0 }.map { $0.element }.sorted())
let canonicalForm = evenChars + oddChars
uniqueForms.insert(canonicalForm)
}
return uniqueForms.count
}Ставь 👍 и забирай 📚 Базу знаний