Задача с собеседования в Zopsmart

Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.

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

Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?

Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"

Пример 2:
Input: s = " hello world "
Output: "world hello"

Пример 3:
Input: s = "a good example"
Output: "example good a"

Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Так как в питоне строки неизменяемы, мы не можем реализовать решение in-place с O(1) дополнительной памяти.
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).

Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова

Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.

Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!

Сложность
O(n) - по времени (сплит и обход списка строк)
O(n) - по памяти (храним список строк)

Код
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1

while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1

return " ".join(words)

@algoses