LeetCode 0151. Reverse a string of words

【LetMeFly】151.颠倒字符串中的单词

力扣题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

给你一个字符串 s ,颠倒字符串中 单词 的顺序.

单词 是由非空格字符组成的字符串.s 中使用至少一个空格将字符串中的 单词 分隔开.

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串.

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格.返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格.

 

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格.

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格,颠倒后的字符串需要将单词间的空格减少到仅有一个.

 

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

 

进阶：如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O(1) 额外空间复杂度的 原地 解法.

方法一：栈

Traverse each character from back to front,遇到非空格字符就入栈,遇到空格/Traverse to the beginning of the string It depends on whether the stack is empty

如果栈不空,Add the new word on the stack just after the answer string

添加方式为：(If the word is not the first word of the answer string,just add spaces.)Pop the stack one by one and add to the end of the answer string

• 时间复杂度$O(n)$,其中$n$is the length of the original string
• 空间复杂度$O(m)$,其中$m$is the maximum word length

AC代码

C++

class Solution {
    
public:
    string reverseWords(string s) {
    
        string ans;
        stack<char> st;
        for (int i = s.size() - 1; i >= 0; i--) {
    
            if (s[i] != ' ')
                st.push(s[i]);
            if (s[i] == ' ' || !i) {
    
                if (st.size()) {
    
                    if (ans.size())
                        ans += ' ';
                    while (st.size()) {
    
                        ans += st.top();
                        st.pop();
                    }
                }
            }
        }
        return ans;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126093751