Какие знаешь способы развернуть порядок слов в строке?

Развёртывание порядка слов в строке

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

Способ 1: Split + Reverse + Join (самый простой)

Это самый читаемый способ для production-кода:

public static String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    List<String> list = Arrays.asList(words);
    Collections.reverse(list);
    return String.join(" ", list);
}

Преимущества:

• Минимум кода, максимум читаемости
• Автоматически обрабатывает множественные пробелы
• Понятен любому разработчику

Недостатки:

• O(n) дополнительная память на новый массив
• Медленнее на очень больших строках

Способ 2: Два двойных разворота (O(1) память)

Элегантный алгоритм, используемый в embedded-системах:

public static String reverseWords(String s) {
    char[] chars = s.toCharArray();
    
    // Шаг 1: развернуть всю строку
    reverse(chars, 0, chars.length - 1);
    
    // Шаг 2: развернуть каждое слово обратно
    int start = 0;
    for (int i = 0; i <= chars.length; i++) {
        if (i == chars.length || chars[i] == ' ') {
            reverse(chars, start, i - 1);
            start = i + 1;
        }
    }
    
    return new String(chars).trim();
}

private static void reverse(char[] chars, int left, int right) {
    while (left < right) {
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        left++;
        right--;
    }
}

Сложность: O(n) время, O(1) дополнительная память

Способ 3: Использование Stack

Наиболее логичный способ для новичков:

public static String reverseWords(String s) {
    Stack<String> stack = new Stack<>();
    String[] words = s.trim().split("\\s+");
    
    for (String word : words) {
        stack.push(word);
    }
    
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
        if (!stack.isEmpty()) {
            result.append(" ");
        }
    }
    
    return result.toString();
}

Способ 4: Итерирование с конца

Прямолинейный подход:

public static String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder result = new StringBuilder();
    
    for (int i = words.length - 1; i >= 0; i--) {
        result.append(words[i]);
        if (i > 0) {
            result.append(" ");
        }
    }
    
    return result.toString();
}

Сравнение подходов

Split + Reverse: Лучше для production, максимальная читаемость. Два разворота: Оптимально по памяти, покажет глубокое понимание алгоритмов. Stack: Хорош на собеседовании, если явно просят использовать Stack. Итерирование: Самый прямолинейный вариант.

Рекомендация на собеседовании

1. Сначала предложи Split + Reverse — покажи базовые знания
2. Потом два разворота — если спросят про оптимизацию
3. Напиши unit-тесты для валидации:

@Test
public void testReverseWords() {
    assertEquals("world hello", reverseWords("hello world"));
    assertEquals("blue is sky The", reverseWords("The sky is blue"));
}

Это покажет понимание алгоритмов, умение оптимизировать, и практический опыт.