Reverse-Words-in-a-String

发表于 | 更新于：

题目地址

LeetCode#151 Reverse Words in a String

题目描述

  Given an input string, reverse the string word by word.

Example: 

1
2
Input: "the sky is blue",
Output: "blue is sky the".

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up: For C programmers, try to solve it in-place in O(1) space.

解题思路

  遍历每一个单字然后保存到栈里再组成一个字符串就OK，直接看代码。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void reverseWords(string &s) {
        stringstream ss;
        stack<string> st;

        for (auto & c : s) {
            if (c == ' ' && !ss.str().empty()) {
                st.push(ss.str());
                ss.str("");
            } else if (c != ' '){
                ss << c;
            }
        }

        if (!ss.str().empty()) st.push(ss.str());

        s = "";

        while (!st.empty()) {
            s += st.top();
            if (st.size() > 1) s += " ";
            st.pop();
        }
    }
};
0%