Сложность: medium
Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.
Пример:
Input: s = "aabb"
Output: ["abba","baab"]
👨💻 Алгоритм:
1️⃣Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s. Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка невозможна, и мы возвращаем пустой список.
2️⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества. Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.
3️⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку. Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома. Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.
😎 Решение:
class Solution:
def __init__(self):
self.set = set()
def generatePalindromes(self, s: str) -> list[str]:
map = [0] * 128
st = [''] * (len(s) // 2)
if not self.canPermutePalindrome(s, map):
return []
ch = ''
k = 0
for i in range(len(map)):
if map[i] % 2 == 1:
ch = chr(i)
for j in range(map[i] // 2):
st[k] = chr(i)
k += 1
self.permute(st, 0, ch)
return list(self.set)
def canPermutePalindrome(self, s: str, map: list[int]) -> bool:
count = 0
for char in s:
index = ord(char)
map[index] += 1
if map[index] % 2 == 0:
count -= 1
else:
count += 1
return count <= 1
def swap(self, s: list[str], i: int, j: int) -> None:
s[i], s[j] = s[j], s[i]
def permute(self, s: list[str], l: int, ch: str) -> None:
if l == len(s):
self.set.add(''.join(s) + (ch if ch != '' else '') + ''.join(s[::-1]))
else:
for i in range(l, len(s)):
if s[l] != s[i] or l == i:
self.swap(s, l, i)
self.permute(s, l + 1, ch)
self.swap(s, l, i)
Ставь 👍 и забирай 📚 Базу знаний