Как сделать из строки палиндром
Обновлено: 07.07.2024
Дана символьная строка, составленная из букв латинского алфавита . Определите наименьшее количество символов , которые необходимо удалить , чтобы из оставшихся получлся палиндром. Укажите удаляемые символы. Текст : "DAKFQNFSK". Рузльтат : нужно выбросить 4 символа , например, N, S, D, A, получится палиндром FKQKF
4 ответа
простейшее что можно придумать правда долгое
выкидываем по очереди всевозможные комбинации букв длин 1,2,3.
плюсы - легко реализовать перебором
ну и будет долго работать - если подумать то наверно как то процесс можно оптимизировать
кстати можно и рекурсивно
выкидываем символ смотрим палиндром или нет
если нет то рекурсивный вызов от оставшегося
для начала можно выкинуть все символы которые встречаются в слове один раз. дальше надо будет думать.
функция, которая определяет, что строка полинром есть в FAQ'е.
Нет, выкидывать ничего не стоит. Приведенный Mr.Hacker пример на это указывает.
Рекурсивный метод (теория и алгоритм) можно стрельнуть на википедии - Задача "Сделай Палиндром".
Табличный метод, исходник у меня валялся, вроде даже рабочий , правда решал не я . но будут вопросы задавай.
int max(int value1, int value2) return ( (value1 > value2) ? value1 : value2);
>
int k[100][100];
const char *s1 = "ASDDFSA"; // Здесь - твои символы (до 100 штук)
int L = strlen(s1);
char *s2 = strdup(s1);
strrev(s2);
По просьбам трудящихся, как и обещал, выкладываю хоть какое-то объяснение привиденного выше кода.
Решение базируется на поиске наибольшей общей подпоследовательности (НОП), алгоритм прямой прогонки. В самом деле, если взять слово в прямом порядке и в обратном порядке, и найти их НОП, то она (подпоследовательность) и будет искомым палиндромом. Массив k - хранит значение максимальных НОП. Очень подробное описание с доказательством можно посмотреть здесь.
По поводу вывода тех букв, которые необходимо удалить тоже невижу особых проблем. Удали из исходной строки те буквы которые есть в палиндроме, оставшиеся выведи.
Программирование и разработка
Когда дело доходит до поиска работы и собеседования по кодированию, вам нужно будет уметь продумывать задачи собеседования на основе алгоритмов перед интервьюером или группой экспертов. Практика с самого начала поможет вам успешно пройти технические собеседования.
Обычный вопрос, который вы можете ожидать от реализации, — это проверка того, является ли строка палиндромом. Чтобы познакомить вас с этой проблемой, мы рассмотрим, что такое алгоритм, и узнаем, как решить эту проблему несколькими способами.
Обновление алгоритмов
Вообще говоря, алгоритм — это набор шагов, необходимых для того, чтобы что-то сделать. Подумайте, что нужно, чтобы испечь торт или поменять масло в машине. Все шаги и все инструменты или ингредиенты, необходимые для того, чтобы эти вещи происходили по порядку, являются частью алгоритма.
На высоком уровне алгоритм — это рецепт или руководство по выполнению ряда шагов, которые позволят решить проблему.
В информатике алгоритмы относятся к последовательности четко определенных инструкций, которые говорят компьютеру, что делать для решения проблемы. Точно так же, как у нас должна быть серия шагов, чтобы испечь торт, нам нужна серия четко определенных инструкций для создания алгоритма, который решит нашу проблему.
Существуют всевозможные алгоритмы, и они обычно возникают на собеседованиях по кодированию. Алгоритмы применяются к разным структурам данных. Итак, мы берем структуру данных и применяем алгоритм для выполнения с ней определенных операций.
В этой статье мы рассмотрим, как управлять строкой с помощью алгоритма, в частности, как проверить, является ли строка палиндромом.
Разбивка задач кодирования
Цель этого алгоритма — ввести строку и использовать функцию, чтобы проверить, является ли это палиндромом.
Палиндром — это слово или фраза, которые читаются одинаково вперед и назад. Когда палиндромы равны длине предложения, они игнорируют заглавные буквы, пунктуацию и границы слов.
Например: гоночный автомобиль, 1001, 11.11.11 или 11:11.
Подсказка
Для заданного значения напишите функцию, которая будет проверять, является ли строка палиндромом или нет. Верните, trueесли это так или falseнет.
Подход
Есть несколько различных подходов к решению этой проблемы, которые мы рассмотрим ниже. Но сначала давайте поговорим об этом так, как если бы мы просто объясняли ответ кому-то без кода.
Итак, нам дана ценность. Что это за ценность? Это строка? Это что-то еще?
В приглашении не указывается тип значения. Если бы вы были в ситуации собеседования, это могло бы быть место, где вы могли бы подтвердить интервьюеру, является ли данное значение строкой.
Поскольку палиндром технически может быть чем угодно, давайте разберемся со всеми типами и рассмотрим все крайние случаи. В большинстве случаев на техническом собеседовании вам не нужно беспокоиться о крайних случаях, но интервьюер заметит, если вы скажете об этом.
Напишите функцию, которая будет проверять, является ли это значение палиндромом. Это должно указывать на то, что им нужно логическое значение ( Trueили False).
То, что мы знаем на данный момент:
- Наше значение может быть строкой, числом или объектом
- Нам нужно вернуть логическое значение
- Палиндром игнорирует регистр, пробелы и знаки препинания.
Псевдокод
Во-первых, нам нужно рассмотреть тип значения.
- Если это число, нам нужно преобразовать его в строку, чтобы сравнить, как оно читается в прямом и обратном направлениях.
- Если это объект, нам нужно как-то изменить его на строку, чтобы провести сравнение.
- А также если это строка, мы можем двигаться вперед.
- Если у нас есть null или undefined, как мы с этим справимся?
После того, как мы выяснили тип и изменили его на строку, нам нужно подготовить строку, чтобы мы могли читать ее слева направо и справа налево без каких-либо не буквенно-цифровых символов.
Нам нужно позаботиться об удалении всего постороннего. Мы можем сделать это несколькими способами, например, перебирая строку для удаления определенных символов.
Также мы должны позаботиться о том, чтобы игнорировать буквы, прописные или строчные. Мы можем сделать это, сделав все заглавными или строчными буквами.
Как только все символы, отличные от буквенно-цифровых, исчезли и у нас есть строки в одном корпусе, теперь наша строка готова к тестированию !
Подумайте о возможных способах решения этой проблемы:
- Сравните строку с ее обратной версией (методы JS)
- Выполните итерации, используя цикл for, и проверьте, есть ли символ на другой стороне строки ===
- Используйте рекурсию, чтобы проверить первую и последнюю буквы перед повторным вызовом функции с сокращенной строкой
Настройка кода JavaScript
Есть несколько способов решить эту проблему. Пока вы можете объяснить свой подход и прийти к правильному ответу, ваш подход, вероятно, будет в порядке. Это всего лишь три возможных способа выяснить, является ли переданное значение палиндромом или нет.
Независимо от вашего подхода, установка требует, чтобы мы подготовили значение для тестирования. Давайте продолжим и сделаем это сейчас. Это будет одинаково для всех трех решений.
Вводится строка. Удалить из нее все пробелы. После этого определить, является ли она палиндромом (перевертышем), т.е. одинаково пишется как с начала, так и с конца.
Для удаления пробелов надо перебрать по символам строку. Если очередной символ пробел, то удалить его. При этом следующий символ окажется на месте текущего, а значит не следует увеличивать значение счетчика. Если очередной символ не пробел, то надо перейти к проверке следующего, т.е. увеличить значение счетчика.
Для проверки, является ли строка палиндромом, надо сравнить первую и вторую половины строк. При этом половинки сравниваются так, что первый символ сравнивается с последним, второй — с предпоследним, третий — с третьим с конца, и т. д. То есть если длина строки l, а символ первой половины i, то символ второй половины имеет индекс l-i+1.
Авторизуясь в LiveJournal с помощью стороннего сервиса вы принимаете условия Пользовательского соглашения LiveJournal
специально для gwean и mym_kak_mym
Лена набила рожу мужу - муж орал и банан ел. ( Михаил Фельдман )
1. Допустим, что исходное слово при построении палиндрома Лена.
2. Запишем его дважды одно под другим в две строки:
4. Соберем все в одно целое, читая теперь уже только слева направо в одну строчку: Лена … анел.
5. Если левая часть (аверс) - исходное слово - была осмысленна изначально: Лена, то правая (реверс) получилась явно бессмысленной: анел.
7. Сборка: Лена … - ан ел.
8. Согласовывая Субъект Лена и Предикат ел - получим: Лена … ел(а).
9. Соответственно согласованная флексия -а симметрично породит союз А в начале Предложения в общем случае: А Лена … -ан ел(а), или слово, начинающееся на А-, если повезет: Алена … -ан ел(а)
10. Если исходить из семантической матрицы Предложения SVO: Субъект Предикат(глагол) Объект, то здесь заполнены только 2 места - SV, а место Объекта (Лена ела Что?) свободно.
11. Материализуем Объект: А Лена … БАН ан ел(а).
12. Тогда слева возникает паразитный морф НАБ- .
13. В нем сразу же материализуется [НА] = 1) предлог на или 2) префикс на-.
14. Далее возникает альтернатива: 1) остаться в пределах одного простого Предложения SVO, выбрав предлог на, задающий косвенный падеж периферийного участника, что-то типа А Лена НА Б ОКУ/ Б АЗАРЕ / Б ИДЕ … БАН ан ела (Ср.: А Лена на боку, суко!, банан ела!) или 2) выбрав префикс на-, ввести новый Предикат и тем самым перейти к сложному Предложению SVO1- SVO2 или хотя бы причастному обороту SVO1,VO2 (Ср.: А Лена, набрав чвар, банан ела!) .
15. Если выбран второй Предикат наб-, первоначальное Предложение разрушается и возникает 2 новых: А Лена НАБИЛА … -АЛ И БАН ан ел(а) с незаполненными ячейками семантической матрицы: SV?1… ?OV2.
16. Что же такое набила Лена? Первое, что приходит в голову - идиома Набила морду! (Ср.: Лена, набила рот - оря, рот орал - и банан ел!) .
17. Поскольку ничего путного при обратном чтении не материализуется, попробуем синоним морду=рожу: Набила рожу!
18. Сборка: А Лена набила рожу… уж орал и банан ел(а).
19. Поскольку явно намечаются однородные предикаты орал и ел в левой части, проведем рассогласование - уберем флексию -а и соответственно уйдет союз А слева: Лена набила рожу… уж орал и банан ел.
20. В первом Предложении не хватает только Адресата (набила рожу Кому?). Если Субъектом второго Предложения считать ужа, то конечно - ужу! Тем более что это просто пробка в дырке челюстно-лицевого палиндрома.
21. Сборка: Лена набила рожу ужу, уж орал и банан ел.
22. Но тут есть противоречие: рожа - неприятное лицо, а лицо только у человека, а у ужа - морда, да и орать он может только чисто метонимически-метафорически (издавал звук), скорее - шипел, и не факт еще, что ужи питаются бананами! Да и как можно набить маленькую мордочку ужа, да и чем? Тут налицо разные семантические миры!
23. Слава богу, что центр палиндрома можно заполнить добавлением одной согласной (материализовать слово Муж), и соответственно Адресатом будет Мужу, что сразу же исправляет семантический мир: у мужа и [жена] Лена, и рожа, которую легко набить, так, что он будет орать, да и банан - вполне его еда.
24. Сборка: Лена набила рожу мужу, муж орал - и банан ел.
25. А полная семантическая экспликация: [Жена] Лена набила рожу [своему] мужу, [в результате чего] муж орал - и [потом] банан ел.
26. Если отключиться от конкретики, то в Предложении кроме Субъект-Предикат-Объектных отношений выражаются отношения Родства, Принадлежности, Причины-Следствия, Следования.
27. Т.о. вырисовываются семантические приемы построения палиндрома: бустрофедон, сборка, материализация слова, согласование, рассогласование, заполнение семантической матрицы простого предложения SVO, преобразование одной группы SVO простого предложения в несколько групп SVO1, SVO2 и т.д. сложного предложения, идиомы, синонимы, однородные члены, поиск периферийных участников при заполненной матрице SVO, однородный семантический мир, образность.
28. Но м.б. есть смысл идти от предикатов (глаголов)? Если здесь идти от фразы: набила рожу мужу, или хотя бы устойчивой синтагмы набила рожу, то это автоматически породит всю фразу: 1) набила рожу …; 2) набила рожу … М уж орал и бан-; 3) ЛЕНА набила рожу … Муж орал и бан АН ЕЛ ; 4) Лена набила рожу МУЖУ муж орал и банан ел.
Читайте также: