Это из GeeksForGeeks:
«По заданной строке найдите самый длинный палиндром, который можно построить, удалив или перетасовав символы из строки. Вернуть только один палиндром, если существует несколько строк палиндрома наибольшей длины».
Учитывая их примеры ввода и вывода, я собираюсь предположить, что вводит только строчные буквы. Если вы хотите предположить обратное, следующая запись в блоге все равно будет релевантной на 99%.
Вот мой псевдокод для наивной реализации:
# remember: palindromes must have the same letter at [0] and [-1], [1] and [-2], etc. # scan the string for duplicate letters # return a single letter if no duplicate letters exist # when a pair of letters is found, add them to beginning and end of new string, and remove them both from the original string # if, when no pairs are left, there are still characters remaining in the string, add one of them to the string at index [string.length/2]
Итак, с этим хакерским планом я пришел к следующему:
def longest_pal(str)
longest = []
loop do
alpha = str.scan(/([a-z])/)[0][0]
all_of_alpha = str.scan(/#{alpha}/)
letter = all_of_alpha[0]
if all_of_alpha.length >= 2
remaining = all_of_alpha.length - 2
longest.insert(0, letter)
longest.insert(-1, letter)
str.delete!(letter)
remaining.times do
str << letter
end
end
break unless str.each_char.find { |c| str.count(c) > 1 }
end
letter = str.scan(/([a-z])/)[0][0]
longest.insert(longest.length/2, letter) unless str.empty?
longest.join
end
Что тут происходит? Что ж, мы #сканируем любую букву в строке. Затем мы сопоставляем все экземпляры этой буквы. Если есть два или более экземпляра, мы добавляем эту букву в начало и конец массива, #удаляем все экземпляры этой буквы из строки, затем добавляем ее обратно, чтобы в итоге мы удалили только 2. Мы прерываем работу, когда есть пар больше не осталось, затем добавьте последнюю букву в середину строки, если какие-либо буквы остались.
Ой. Но эй, это работает. Теперь давайте посмотрим, что говорят люди GeeksForGeeks.
«Для палиндромной строки нечетной длины, скажем, 2n + 1, 'beg' состоит из первых n символов строки, 'mid' будет состоять только из 1 символа, т.е. (n + 1)-й символ, а 'end' будет состоять из из последних n символов строки-палиндрома.
Похоже, мы были на правильном пути. GeeksForGeeks дает нам реализацию на C++, которую я преобразовал в Ruby ниже:
def longest_pal(str)
beg = ""
mid = ""
count = {}
i = 0
while i < str.length
count[str[i]] ||= 0
count[str[i]] += 1
i += 1
end
count.keys.each do |letter|
if count[letter].odd?
mid = letter
count[letter] -= 1
else
i = 0
while i < count[letter]/2
beg << letter
i += 1
end
end
end
last = beg.reverse
"#{beg}#{mid}#{last}"
end
Какая разница? Первое, что бросается в глаза, это использование ими хеша. Они проходят через строку один раз, увеличивая количество для этой буквы. Затем они проверяют, добавляют ли буквы в начало строки, если количество букв четное. Если нечетное, они устанавливают среднюю букву на эту букву. В конце они переворачивают начальную строку и объединяют все три части в один палиндром. Решение — O(n), потому что задействована только одна итерация, а обращение массива, дающее нам «последний» компонент, происходит только один раз. Сравните это с моей первой попыткой, которая включала 2 сканирования каждой пары букв в строке. Мне кажется, что это как минимум O(2n), и при этом выглядит намного уродливее. Держитесь подальше от регулярных выражений, дети. Ты не хочешь закончить, как я.
