翻转字符串里的单词

约定不等于承诺〃 2023-02-17 12:26 6阅读 0赞

# 一、前言 #

问题来源LeetCode

问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1011/][https_leetcode-cn.com_explore_interview_card_bytedance_242_string_1011]

## 二、题目 ##

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1:

输入: "the sky is blue"
    输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

*  无空格字符构成一个单词。
 *  输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *  如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

## 三、思路 ##

逆序打印字符串，用栈实现简单直观，解法一的思路。可以在解法一的基础上优化，将字符串从后往前截取，然后将截取的字符串拼接在一起即可

## 四、编码实现 ##

//==========================================================================
    /**
    * @file : 05_ReverseWords.h
    * @title: 翻转字符串里的单词
    * @purpose : 给定一个字符串，逐个翻转字符串中的每个单词。
    *
    * 示例 1:
    * 输入: "the sky is blue"
    * 输出: "blue is sky the"
    *
    * 示例 2:
    * 输入: "  hello world!  "
    * 输出: "world! hello"
    * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    *
    * 示例 3:
    * 输入: "a good   example"
    * 输出: "example good a"
    * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
    
    * 说明：
    * 无空格字符构成一个单词。
    * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
    *
    * 来源：力扣（LeetCode）
    * 链接：https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1011/
    * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    */
    //==========================================================================
    #pragma once
    #include <stack>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    #define NAMESPACE_REVERSEWORDS namespace NAME_REVERSEWORDS {
    #define NAMESPACE_REVERSEWORDSEND }
    NAMESPACE_REVERSEWORDS
    
    // 方法一：用栈辅助解决
    class Solution_1
    {
    public:
        string reverseWords(string s)
        {
            if (s.empty())
                return s;
    
            stack<string> st;
            string str;
            for (int i = 0; i < s.length(); ++i)
            {
                if (s[i] == ' ')
                {
                    if (!str.empty())
                    {
                        st.push(str);
                        str.clear();
                    }
    
                    continue;
                }
                else
                {
                    if (str.empty())
                        str = s[i];
                    else
                        str += s[i];
                }
            }
    
            if (!str.empty())
                st.push(str);
    
            string result;
            while (!st.empty())
            {
                if (result.empty())
                    result = st.top();
                else
                    result = result + " " + st.top();
    
                st.pop();
            }
    
            return result;
        }
    };
    
    // 方法二：将字符串从后往前截取，然后将截取的字符串拼接在一起
    class Solution_2
    {
    public:
        string reverseWords(string s)
        {
            if (s.size() == 0)
                return s;
    
            string res = "";
            int i = (int)s.size() - 1;
            int len = 0;
            for (; i >= 0; i--)
            {
                if (len != 0 && s[i] == ' ')
                {
                    res += s.substr(i + 1, len);
                    res += ' ';
                    len = 0;
                    continue;
                }
                if (s[i] != ' ') len++;
            }
            if (len != 0) res += s.substr(0, len) + ' ';
            if (res.size() != 0) res.pop_back();
            return res;
        }
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, string s, string& expect)
    {
        Solution_1 S1;
        Solution_2 S2;
        string result1 = S1.reverseWords(s);
        string result2 = S2.reverseWords(s);
    
        if (result1 == expect && result2 == expect)
            cout << testName << ", solution12 passed." << endl;
        else
            cout << testName << ", solution failed. result1:" << result1 << ", result2:" << result2 << " ,expect:" << expect << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string s = "0";
        string expect = "0";
    
        test("Test1()", s, expect);
    }
    
    void Test2()
    {
        string s = "the sky is blue";
        string expect = "blue is sky the";
    
        test("Test2()", s, expect);
    }
    
    void Test3()
    {
        string s = "  hello world!  ";
        string expect = "world! hello";
    
        test("Test3()", s, expect);
    }
    
    void Test4()
    {
        string s = "a good   example";
        string expect = "example good a";
    
        test("Test4()", s, expect);
    }
    NAMESPACE_REVERSEWORDSEND
    // 测试 用例 END
    //
    
    void ReverseWords_Test()
    {
        NAME_REVERSEWORDS::Test1();
        NAME_REVERSEWORDS::Test2();
        NAME_REVERSEWORDS::Test3();
        NAME_REVERSEWORDS::Test4();
    }

**执行结果：**

![20200614085359868.png][]

[https_leetcode-cn.com_explore_interview_card_bytedance_242_string_1011]: https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1011/
[20200614085359868.png]: https://img-blog.csdnimg.cn/20200614085359868.png