186. Reverse Words in a String II

public class Solution {
    public void ReverseWords(char[] s) {
        Array.Reverse(s);
        int start = 0, end = 0, n = s.Length;
        while (start < n) {
            while (end < n && s[end] != ' ') end++;
            Array.Reverse(s, start, end - start);
            end++;
            start = end;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void ReverseWords(char[] s) {
        Array.Reverse(s);
        int start = 0, end = 0, n = s.size();
        while (start < n) {
            while (end < n && s[end] != ' ') end++;
            Array.Reverse(s, start, end - start);
            end++;
            start = end;
        }
    }
}

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);
    }
}

class Solution {
    reverseWords(s) {
        s.reverse();
        let start = 0, end = 0, n = s.length;

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

class Solution:
    def reverse(self, l: List[str], left: int, right: int) -> None:
        while left < right:
            l[left], l[right] = l[right], l[left]
            left, right = left + 1, right - 1

    def reverse_each_word(self, l: List[str]) -> None:
        n = len(l)
        start = end = 0

        while start < n:
            while end < n and l[end] != ' ':
                end += 1
            self.reverse(l, start, end - 1)
            start = end + 1
            end += 1
            
    def reverseWords(self, s: List[str]) -> None:
        self.reverse(s, 0, len(s) - 1)
        self.reverse_each_word(s)

func reverseWords(s []byte) {
    reverse := func(s []byte) {
        for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
            s[i], s[j] = s[j], s[i]
        }
    }

    reverse(s)
    start, n := 0, len(s)
    for start < n {
        end := start
        for end < n && s[end] != ' ' {
            end++
        }
        reverse(s[start:end])
        start = end + 1
    }
}

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎