1

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

На вход подается единственная строка, состоящая из слов, разделенных пробелами. Выведите 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-й, я пока не понимаю. Прошу помочь.

Kromster
  • 13,809
Hashirama
  • 187
  • 3
    @Hashirama, зачем так сложно?
    1. Строка разбивается на слова (метод .split(), если не ошибаюсь)
    2. Полученный массив переворачивается.
    3. Создается новая строка и сравнивается с оригинальной либо перевернутый массив сравнивается с оригинальным.
     – etki Sep 10 '14 at 08:59
  • Почему так сложно? Не знаю, могу выделить две причины:
    1. я не знаком с "инструментами", с помощью которых можно проще;
    2. тупо не могу догадаться до более простого метода.

    Поясните, что Вы подразумеваете под "переворачиванием" массива.

     – Hashirama Sep 10 '14 at 09:03
  • Эмъ... Может быть: 
    txt = 'so patient a doctor to doctor a patient so'
txt_arr = txt.split('\s')
txt_arr_reverse = list(txt_arr)
txt_arr_reverse.reverse()
print 'YES' if txt_arr == txt_arr_reverse else 'NO'

    Т.е. преобразовали в массив, сделали копию массива и сравнили исходный массив и перевернутую копию - если равны, значит все ОК.

    Так пойдет?

     – BOPOH Sep 10 '14 at 09:05
  • Да, но поясните, что делает вторая строка Вашего кода. И четвертая. – Hashirama Sep 10 '14 at 09:09
  • 2 строка разбивает текст на массив слов по разделителю (у меня там ошибка, сейчас исправлю).
    4 строка переворачивает массив.

    Лучше запустите и посмотрите, что происходит, сами.

     – BOPOH Sep 10 '14 at 09:11
  • @BOPOH, 
    txt_arr = txt.split(' ')
txt_arr_reverse = list(txt_arr)

    Вообще-то split и так в результате дает список.

     – insolor Sep 10 '14 at 12:48
  • @insolor, а вас не смущает следующее: 
    a = [1, 2, 3]
b = a
a[0] = 3 # <- a = [3, 2, 3], b = [3, 2, 3]
b[1] = 3 # <- a = [3, 3, 3], b = [3, 3, 3]

    Если не заметили, далее я сравниваю txt_arr и txt_arr_reverse. Чтобы txt_arr_reverse.reverse() так же не менял и txt_arr (а значит сравнение было бы бесполезным) я и использую клонирование списка (т.е. list от списка)

    UPD: avp, а кто спорит? У любой задачи есть если не куча, то хотя бы несколько решений, взять хотя бы swap. Даже для вашего варианта есть несколько способов реализации. Я же просто привел один из способов.

     – BOPOH Sep 10 '14 at 13:49
  • @BOPOH, тут вообще не нужны 2 списка. Достаточно одного. Просто сравниваете слова с начала списка со словами в его же конце. – avp Sep 10 '14 at 13:55
  • @BOPOH, тогда вот так, без дополнительной переменной: txt_arr == list(reversed(txt_arr)). А вообще, конечно, способов реализации довольно много. – insolor Sep 11 '14 at 04:16
  • Комментарии появились ))

    @insolor, да кто же спорит? Я могу кучу вариаций привести (с различными if`ами только несколько штук), здесь сама идея важна - я ее на конкретном примере и показал.

    А вообще - я комментарием выше про это уже писал.

    Если же вы про мой ответ вам, то я ваш комментарий понял буквально - "txt_arr уже список, поэтому list(txt_arr) можно заменить на txt_arr". Но ведь в данном случае работа алгоритма сломается, на что я и указал.

     – BOPOH Sep 11 '14 at 04:18

4 Answers4

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
  • профит
Виталина
  • 11
Александр Молофеев
  • 2,346
  • 14
  • 19
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
jfs
  • 52,361
1

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

Виталина
  • 11
JimmDiGriz
  • 1,349
  • Вы на пример внимательно посмотрите. С чем в таком случае сравнивать "to"? – Hashirama Sep 10 '14 at 09:05
  • Само с собой сравнится. Не волнуйся, прокатит. Выше господин указывал на метод split(). Разбив им строку на слова, вполне можно будет их сравнить между собой. – JimmDiGriz Sep 10 '14 at 09:06
0

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

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

Виталина
  • 11
igaraev
  • 471
  • 1
    Удалять пробелы ни в коем случае нельзя. Иначе у вас неверно сработает строка

    so patient a doctor to doctor apatient so

     – LinnTroll Sep 10 '14 at 09:36
  • 1
    А разве палиндром это "to be be to"? Я че-то думал, что "to be eb ot". – BOPOH Sep 10 '14 at 10:25
  • Ну, палиндром может быть как из букв ("abcd dcba"), так и из слов ("a1 a2 a2 a1"). ТС нужен палиндром из слов. Поэтому количество пробелов между словами роли не играет.

    --

    Определить, является ли строка палиндромом из букв, вообще очень просто (на Си)

     int is_palindrome (const char *s) {
     int i = 0, j = strlen(s);

     while (i < j)
      if (s[i++] != s[--j])
         return 0;
     return 1;
 }

    Алгоритм для палиндрома из слов -- совершенно аналогичный, только надо передать массив слов и его размер и сравнивать слова, а не символы.

     – avp Sep 10 '14 at 13:02