Блог

Я пытаюсь выучить Python, и поэтому я столкнулся с проблемой: для моих курсов есть требования: максимальное время 1 сек и максимальная память 512 МБ. Задача состоит в том, чтобы найти наименьший палиндром в алфавитном порядке. минимальная длина для палиндрома равна 2. например: ghghwwdkjnccjknjn вот: ghg, cc, ww, njn. Нам нужен наименьший — cc или ww — в алфавите c перед w (как в словарях). aba находится перед aca (c> b) и так далее

Вот мой код:

 s = input("")
lst = []
for i in range(0, len(s)):
    for j in range(i   1, len(s)   1):
        p = s[i:j]
        if p == p[::-1] and len(p)>=2:
            lst.append(p)
            lst.sort()
        del p
if not lst:
    print("-1")
else:
    #lst.sort()
    print(sorted(lst, key = len)[0])
  

Таким образом, я получаю 1.088s 9.89Mb, а при перемещении lst.sort() в конец я получаю 0.901s 527.30Mb — оба плохие. Как я могу сделать это лучше? Спасибо!

Эффективная чистая реализация всех улучшений, упомянутых ниже:

 def substrings(string, length):
    for i in range(len(string) - length   1):
        yield string[i : i length]

def palindromes(strings):
    for string in strings:
        if string == string[::-1]:
            yield string

def best_palindrome(string):
    for length in 2, 3:
        if result := min(palindromes(substrings(string, length)), default=None):
            return result
    return -1

print(best_palindrome(input()))
  

Принят в Code Forces с 218 мс и 796 КБ (с использованием Python 3.7.2).

Возможно, самая простая модификация, которая сделает его намного более эффективным, — это добавить это в качестве первого элемента в j цикле:

         if j - i > 3:
            break
  

То есть не проверяйте длины выше 3. Потому что любой более длинный палиндром, такой как abba или abcba, содержит более короткий, например, bb или bcb в этих случаях. Поскольку вам все равно нужен самый короткий, любые более длинные всегда бесполезны.

Кроме того, выполняйте сортировку только в конце, а не после каждого добавления.

С этими двумя изменениями я получил его в Code Forces (ссылка из вашего комментария ниже).

Дальнейшие возможные улучшения:

• Не сортируйте, просто получите минимум.
• Начните j с at i 2 вместо at i 1 и снимите len(p)>=2 флажок.
• Для уменьшения объема памяти не собирайте все в список (используйте набор или создавайте кандидатов в генераторе).
• Сначала попробуйте только все подстроки длиной 2, и только если это не удастся, попробуйте длину 3.