Развернуть слова в строке

Есть строка состоящая из слов разделённых пробелами. Нужно развернуть слова.

Важно — не буквы в каждом слове, они должны остаться на месте, а сами слова. Лучше всего понять на примере:

Input: "the sky is blue"
Output: "blue is sky the"

Пробелы в начале и конце предложения нужно убрать:

Input: "  hello world!  "
Output: "world! hello"

Аналогично и пробелы между словами:

Input: "a good   example"
Output: "example good a"

Нужно решить без дополнительной памяти.

Решение

В принципе, основная сложность — решение без дополнительной памяти (строго говоря в текущей постановке на JavaScript этого сделать нельзя, но на собеседовании можно сделать некоторые допущения относительно входных данных), но всё по порядку. Обсудим сперва тривиальное решение.

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
	return s.split(' ').filter(Boolean).reverse().join(' ');
};

Решение вполне себе рабочее, ничего плохо в нём нет, если что. Единственное, что нужно понимать (и рассказать), что split — создаёт новый массив, разбивая строку по пробелам. Это и есть «дополнительная память», использование которой нужно избежать. Об этом нужно явно сказать и перейти к другому решению.

Я сказал выше, что в данной постановке задачи решить на JavaScript без дополнительной памяти не получится. Всё потому строки неизменяемые. Можно сделать следующее допущение — на вход нам приходит не строке, а массив символов, с которым и нужно работать in-place.

Кажется, я уже рассказывал о in-place алгоритмах, зачастую это требуется в задачах на строки. Суть в том, что результат нужно накапливать в исходном массиве, переставляя элементы или используя свободное место.

Суть in-place решения в следующем:

Источник

Источник