Leetcode: Reverse Words in a String

卡尔曼和玻尔兹曼谁曼

发布于 2019-01-22 17:22:43

3540

发布于 2019-01-22 17:22:43

文章被收录于专栏：给永远比拿愉快给永远比拿愉快

题目： Given an input string, reverse the string word by word.

For example, Given s = “the sky is blue”, return “blue is sky the”.

思路一：先休整下给定的字符串，去掉其中的多于一个的空格，就是使所有单词之间的空格都变成一个，然后去掉最后面的空格，给最前面加一个空格。这样每次遇到空格的时候，前面的子串就是一个完整的单词。 C++代码实现（用时9ms）：

class Solution
{
public:
    void reverseWords(string &s)
    {
        //去掉所有多于一个的空格
        for (size_t i = 1; i < s.length(); i++)
        {
            if (s[i - 1] == ' ' && s[i] == ' ')
            {
                s.erase(s.begin() + i);
                --i;
            }
        }
        //如果前面没有空格，给前面加一个空格
        if (s.front() != ' ') s.insert(0, " ");
        //如果后面有空格，去掉后面空格
        if (s.back() == ' ') s.pop_back();
        if (s.length() <= 1) return;
        vector<string> words;
        int start = int(s.length() - 1);
        //从后往前遍历
        for (int i = start; i >= 0; --i)
        {
            if (s[i] == ' ')
            {
                words.push_back(s.substr(i + 1, start - i));
                if (i != 0) start = i - 1;
            }
        }
        s.clear();
        size_t size = words.size();
        for (size_t i = 0; i < size; i++)
        {
            s += words[i];
            s.push_back(' ');
        }
        //去掉最后一个多余的空格
        s.pop_back();
    }
};

思路二：维护两个栈，当是不是空格的时候压入单词栈，当是空格的时候压入句子栈。这个的好处就是不用预先处理给定的的字符串。 C++实现代码（用时24ms，可能是栈的开销比较大吧）：

class Solution
{
public:
    void reverseWords(string &s)
    {
        s += ' ';//因为当s[i]是空格的时候前面的字符串是一个单词，为了好判断给字符的后面加一个空格
        size_t length = s.length();
        stack<char> words;
        stack<char> sentence;
        for (size_t i = 0; i < length; i++)
        {
            //如果不为空格，压入words栈中
            if (s[i] != ' ') words.push(s[i]);
            //如果是空格且words不为空的话，将words中的字符压入sentence栈中且在sentence后面添加空额
            //如果是空格但是words为空则什么都不做
            else
            {
                bool flag = false;
                while (!words.empty())
                {
                    flag = true;
                    sentence.push(words.top());
                    words.pop();
                }
                if (flag) sentence.push(' ');
            }
        }
        s.clear();
        //如果sentence不为空，后面肯定有一个多余的空格，去掉最后的空格
        if (!sentence.empty()) sentence.pop();
        while (!sentence.empty())
        {
            s += sentence.top();
            sentence.pop();
        }
    }
};

C#代码（思路一解法）：

public class Solution
{
    public string ReverseWords(string s)
    {
        if (s.Length == 0) return string.Empty;
        StringBuilder result = new StringBuilder(s);
        //去掉多于一个的空格
        for (int i = 1; i < result.Length; i++)
        {
            if (result[i - 1] == ' ' && result[i] == ' ')
            {
                result.Remove(i, 1);
                --i;
            }
        }
        if (result[0] != ' ') result.Insert(0, ' ');
        if (result[result.Length - 1] == ' ') result.Remove(result.Length - 1, 1);
        if (result.Length <= 1) return result.ToString();
        s = result.ToString();
        List<string> words = new List<string>();
        int start = result.Length - 1;
        for (int i = start; i >= 0; --i)
        {
            if (result[i] == ' ')
            {
                words.Add(s.Substring(i + 1, start - i));
                start = i - 1;
            }
        }
        result.Clear();
        foreach (string item in words)
        {
            result.Append(item);
            result.Append(' ');
        }
        result.Remove(result.Length - 1, 1);
        return result.ToString();
    }
}

Python代码：

class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        if len(s) == 0:
            return ''
        words = s.split(' ')
        i = 0
        while i < len(words):
            if words[i] == '':
                del words[i]
            else:
                i = i + 1
        if len(words) == 0:
            return ''
        words.reverse()
        result = ''
        for item in words:
            result = result + item + ' '
        return result[:len(result) - 1]

显然，Python代码要简洁地多！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2015年03月31日，如有侵权请联系 cloudcommunity@tencent.com 删除

c++