算法:翻转单词顺序列

翻转单词顺序列

翻转单词顺序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。

后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

分析

先翻转整个字符串, 然后再翻转每一个单词(按照空格拆分)

需要注意的是, 最后一个单词结尾没有空格, 做特殊处理即可!

代码

public class Solution {
    public String ReverseSentence(String str) {
        if (str == null) return null;

        int len = str.length();
        if (len <= 1) return str;

        char[] arr = str.toCharArray();
        // 整个翻转
        reverse(arr, 0, len - 1);

        // 翻转每个单词
        int blankIndex = -1;
        for (int i = 0; i < len; ++i) {
            if (arr[i] == ' ') {
                int next = i;
                reverse(arr, blankIndex + 1, next - 1);
                blankIndex = next;
            }
        }

        // 翻转最后一个单词(末尾无空格)
        reverse(arr, blankIndex + 1, len - 1);
        return new String(arr);
    }

    // 翻转 [left, right]
    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}