Эта статья содержит несколько забавных обсуждений алгоритмов того, как перевернуть слова предложения. Это популярный вопрос на собеседовании, и я расскажу о деталях этой проблемы и о том, как к ней подойти, а также о некоторых решениях, написанных на Python и C.

Сопутствующий репозиторий Github доступен здесь: https://github.com/hmurari/reverse-words - отправляйте запросы на вытягивание, если у вас есть интересное решение или решение на другом языке. Я обещаю, что быстро объединю его :-)

Проблема

Обратные слова предложения. Например, если вы получили ввод «вы не должны пройти», он должен вернуть «не проходите».

В качестве бонусной задачи программа должна позаботиться о пунктуации. (Знаки пунктуации должны стоять в том же порядке, что и в исходном предложении). Например - «ты, не проходишь!» должен приводить к «пройти, не так ли!»

Проблема

Python предоставляет множество способов управления строками - и это репо содержит несколько примеров того, насколько мощны регулярные выражения Python и библиотека управления строками.

Разделите предложение, переверните его и присоедините обратно

Начнем сначала с простого метода. Python предоставляет метод split (), с помощью которого мы можем разбивать слова в строке. Тогда все, что нам нужно сделать, это перевернуть этот список и присоединиться к ним.

Как это работает:

  • s.split(' ') разделяет строки, используя пробел в качестве разделительного символа. Он возвращает массив слов, которые были разделены.
  • reversed(list) возвращает перевернутую строку.
  • 'separator'.join(words) соединяет слова с помощью разделителя. В данном случае мы их объединяем пробелом.

Чего ему не хватает:

  • Это не касается пунктуации.
  • "Вы не должны пройти!" будет преобразовано в "пройти!" ты не должен (тьфу)

Используйте модули регулярных выражений Python

Другой простой способ в Python - разделить с помощью модуля регулярных выражений. Это позволит нам разделять как по пробелам, так и по пунктуации.

В этом случае мы хотим найти все слова и знаки препинания и собрать их как разные элементы в массиве. Затем нам нужно просто поменять местами слова, сохраняя при этом знаки препинания на одном и том же месте.

Круто - это хорошее начало. Это регулярное выражение [:;,.!?] позволяет нам изолировать все знаки препинания от строки. Теперь следующий шаг - выделить его вместе со словами в предложении. Перед этим я хотел сделать краткий обзор того, что здесь только что произошло, с точки зрения регулярного выражения.

  • Я использую этот набор {',', '.', '!', ':', ';', '?'} как набор всех знаков препинания - при необходимости вы можете добавить сюда другие знаки пунктуации.
  • Мы используем findall метод re, который позволяет находить все совпадения с заданным регулярным выражением.
  • Квадратная скобка [] необходима для совпадения одного символа с условием ИЛИ. Например, [:;,.!?] совпадает с :|;|,|.|!|?

Приведенный выше фрагмент не содержит фактических слов списка. Это должно быть легко исправить.

Замечательно - теперь нам нужно перевернуть все слова, не являющиеся знаками препинания, и у нас будет окончательная программа. Чтобы сделать разворот - мы будем использовать два указателя: один идет слева направо, а другой - справа налево. Мы меняем местами то, на что указывают эти указатели, когда оба указателя не указывают на знаки препинания.

Это последняя программа.

Третий метод (Regex)

Я ненавижу уродство метода регулярных выражений, представленного выше. Когда я начал писать, мне показалось, что это не должно быть больше 3–4 строк, но это оказалось слишком коряво.

Я чувствую, что сложность возникает из-за того, что знаки препинания должны сохранять свое словесное положение. Я не уверен, что это предположение будет вероятным во многих интервью, поэтому я постараюсь предложить еще одно быстрое решение слегка измененной проблемы.

Допустим, мы изменяем формулировку задачи для знаков препинания следующим образом: знаки пунктуации должны быть связаны с их исходным словом, за исключением конечных, которые всегда должны оставаться в конце. Например, «вы должны, не проходите !!» следует преобразовать в «пройти, не пройдете, вы !!»

На мой взгляд, это, вероятно, даст лучшие бредовые предложения, чем второй метод :-)

С этим определением - мы можем рассматривать все знаки препинания как часть слова, которое они идут после - упрощая нашу логику разделения и обратного. Нам по-прежнему нужно обрабатывать знаки препинания в конце строки отдельно, но это будет всего лишь дополнительная строка кода.

Вот полный код.

Хорошо, это было похоже на три строчки кода! Давайте пройдемся по нему, чтобы увидеть, что он делает.

  • punctuations - это массив всех знаков препинания.
  • Сначала мы пытаемся найти любые знаки препинания в конце строки, чтобы снова добавить их в строку результатов.
  • Символ $ в регулярном выражении указывает, что поиск ведется до конца строки. Мы используем это регулярное выражение для поиска всех знаков препинания в конце строки и сохранения их в строковой переменной.
  • Следующая строка аналогична методу 1 выше - мы удаляем последние знаки препинания, затем разделяем остальные слова. Затем мы переворачиваем этот массив и объединяем его обратно, чтобы получилась строка.
  • Наконец, мы снова добавляем конечные знаки препинания, которые сохранили ранее (end_puncs)

C

С определенно сложнее делать что-то подобное. Вы имеете дело с символами / указателями напрямую и не имеете доступа к красивым библиотекам регулярных выражений. Но это отличный язык для изучения алгоритмов - и мы покажем решение этой проблемы, написанное на C. Вы можете найти исходный код в reverse-words.c в этом репозитории. Это было скомпилировано с помощью компилятора gcc на Mac, но, вероятно, должно работать с Windows так же хорошо.

Первый способ

Сначала я подумал о том, чтобы разделить слова предложения и поместить их в массив указателей на символы. Вскоре моя программа стала слишком громоздкой, с множеством mallocs / frees, множеством циклов и т. Д. Я отказался от этого подхода и попытался разобраться в этой проблеме, выполнив некоторые манипуляции на месте.

Поначалу для простоты - я не буду беспокоиться о пунктуации и постараюсь решить эту проблему без нее. Мы вернемся к проблеме пунктуации позже.

Перевернуть предложение - по буквам - довольно тривиально. Нам просто нужен левый и правый указатели → и продолжайте менять местами символы, пока они не пересекутся. Если вы посмотрите на предложение и перевернутые слова, вы заметите, что есть шаблон, который мы можем использовать.

  • Исходное предложение: «вы не пройдете»
  • Символы перевернуты: ‘ssap ton llahs ouy’
  • Перевернутые слова: «не пройдешь»

Уже при преобразовании символов по символам и в перевернутых словах слова находятся в одном и том же месте - нам просто нужно еще одно обращение для каждого слова, чтобы получить окончательный результат. Таким образом, алгоритм будет выглядеть примерно так:

str <-- 'you shall not pass'
str = reverse(str)  <-- 'ssap ton llahs ouy'
for each word in str {
  reverse(word)
}

А ниже - реализация этой программы на языке C.

Расположение исходного кода Github:

Вы можете найти исходный код всех этих программ по адресу: https://github.com/hmurari/reverse-words

Заключение:

Было очень весело писать различные алгоритмы переворота слов в строке - и я надеюсь, что в будущем добавлю больше такого типа контента. Дайте мне знать, что вы думаете, в комментариях ниже.