Узнать образуют ли введённые слова палиндром

Рейтинг: 1Ответов: 4Опубликовано: 10.09.2014

Итак, есть задача и вот её условие:

На вход подается единственная строка, состоящая из слов, разделенных пробелами. Выведите YES, если после перестановки всех слов строки в обратном порядке получается та же строка, и NO в противном случае.

Например, если вбить

so patient a doctor to doctor a patient so

то программа выведет YES

Для решения задачи я составил алгоритм:

  1. вводится строка;

  2. создается новая строка по следующему принципу:

    2.1. все слова искомой строки, не считая последней, идут вперед, т.е. ставятся перед первой. Пример: последнее слово имеет номер n, тогда слово n-1 ставится перед n, слово n-2 ставят перед n-1 и т.д.;

    2.2. у полученной строки не должно быть пробелов, т.е. все символы стоят в плотную;

  3. у искомой и получившейся строки удаляются все пробелы и затем они сравниваются. Вот собственно и все.

Проблем с реализацией 1-го и 3-го пункта у меня нет, а вот как реализовать 2-й, я пока не понимаю. Прошу помочь.

python алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 3Принят
def validate(string):
    return "YES" if string == " ".join(string.split()[::-1]) else "NO"
print validate("so patient a doctor to doctor a patient so")

Есть как минимум 2 способа инвертировать строку/массив без зауми:

  • reversed(iterable) -> generator object
  • iterable[::-1] -> инвертированный массив/строка

Тогда задача сводится к простому набору шагов:

  • разбить строку на слова (.split() или .split(" ") или можно регулярками)
  • инвертировать получившийся массив
  • склеить обратно через пробел (" ".join(iterable))
  • просто сравнить строки и если True, то вернуть YES, иначе вернуть NO
  • профит
▲ 3

Чтобы проверить, образуют ли данные слова палиндром на Питоне:

#!/usr/bin/env python3
def is_palindrome(seq):
    return seq == seq[::-1]

words = input('Введите слова, разделённые пробелом: ').split()
print("YES" if is_palindrome(words) else "NO")

Особенности:

  • .split() используется вместо .split(' ') , чтобы исключить любые символы пробела.

Чтобы реализовать пункт 2. из вопроса, смотри: Как удалить все пробелы из строки в Python?

Существуют алгоритмы, которые не требуют .split(), которые могут работать без дополнительной памяти, используя только исходную строку (O(1)-space): Efficiently reverse the order of the words (not characters) in an array of characters.

▲ 1

Может, лучше будет сравнивать слова друг с другом? Первое и последнее, второе и предпоследнее и так далее. Все слова равны - YES. Хотя бы одно не равно - NO. Есть и другие варианты. Но это так, я, в общем-то, питон не учил, но полагаю, там так можно.

▲ 0

Задача называется поиск полиндромов.
Удалить все пробелы
"String".replace(' ','')

Можно удалять не просто пробелы, но и все пробельные символы (табуляцию и т.д.).
Для этого нужно изучить регулярные выражения и использовать мождуль re.