Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:
Input: s = ["a"]
Output: ["a"]

👨‍💻 Алгоритм:

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

2⃣Перевернуть каждое слово: пройти по всей строке, идентифицировать границы каждого слова и использовать функцию reverse для переворачивания символов в пределах каждого слова.

3⃣Окончательная корректировка: проверить, чтобы между словами оставался только один пробел, и удалить лишние пробелы в начале и конце строки, если это необходимо.

😎 Решение:
class Solution {
public void reverse(char[] s, int left, int right) {
while (left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
}

public void reverseEachWord(char[] s) {
int n = s.length;
int start = 0, end = 0;

while (start < n) {
while (end < n && s[end] != ' ') ++end;
reverse(s, start, end - 1); start = end + 1;
++end;
}
}

public void reverseWords(char[] s) {
reverse(s, 0, s.length - 1);
reverseEachWord(s);
}
}

Ставь 👍 и забирай 📚 Базу знаний