code4offer-14 翻转单词顺序列

翻转单词顺序列

问题描述

“student. a am I” -> “I am a student.”

分析

临时空间

1
2
3
4
5
6
7
8
9
10
11
public String ReverseSentence(String str) {
    if (str.trim().equals("")) return str;
    String result = "";
    String[] parts = str.split(" ");
    int len = parts.length;
    for(int i = len - 1; i >= 0; --i) {
        result += parts[i];
        if (i != 0) result += " ";
    }
    return result;
}

原地翻转

1
2
3
4
5
6
"student a am I"
"I ma a tneduts"    // 整体reverse
"I ma a tneduts"    // 翻转第一个单词"I"
"I am a tneduts"    // "ma" -> "am"
"I am a tneduts"    // "a" -> "a"
"I am a student"    // "tneduts" -> "student"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void reverseWord(string& str, int start, int end) {
    while (start < end)
        swap(str[start++], str[end--]);
}

string ReverseSentence(string str) {
    reverseWord(str, 0, str.size() - 1);

    int low = 0, high = 0; // 用于确定单词的位置

    int len = str.size();
    for (int i = 0; i < len; ++i) {
        if (str[i] == ' ') {
            high = i-1;
            reverseWord(str, low, high);
            low = i+1;
        }
    }

    reverseWord(str, low, len - 1); // 翻转最后一个单词
    return str;
}