58.1 翻转单词顺序列

题目链接

Leetcode

题目描述

Input:
"I am a student."

Output:
"student. a am I"

解题思路

先翻转整个字符串，再翻转每个单词，最后去掉多余的空格。例如 "I am a student." 整体翻转得到 ".tneduts a ma I"，再逐个翻转单词得到 "student. a am I"。

原书的输入为字符数组，要求只使用该字符数组的空间。Java 的 String 不可变，需要先转成字符数组，空间复杂度为 O(N)，但翻转本身不需要额外空间。

public String reverseMessage(String message) {
    if (message == null) {
        return null;
    }
    char[] chars = message.toCharArray();
    int n = chars.length;

    // 1. 翻转整个字符数组
    reverse(chars, 0, n - 1);
    // 2. 翻转每个单词
    reverseWords(chars, n);
    // 3. 去除多余空格
    return cleanSpaces(chars, n);
}

private void reverseWords(char[] a, int n) {
    int i = 0, j = 0;
    while (i < n) {
        while (i < n && a[i] == ' ') i++;
        j = i;
        while (j < n && a[j] != ' ') j++;
        reverse(a, i, j - 1);
        i = j;
    }
}

private String cleanSpaces(char[] a, int n) {
    int i = 0, j = 0;
    while (j < n) {
        while (j < n && a[j] == ' ') j++;
        while (j < n && a[j] != ' ') a[i++] = a[j++];
        while (j < n && a[j] == ' ') j++;
        if (j < n) a[i++] = ' ';
    }
    return new String(a, 0, i);
}

private void reverse(char[] c, int i, int j) {
    while (i < j) {
        char t = c[i];
        c[i] = c[j];
        c[j] = t;
        i++;
        j--;
    }
}