Leetcode: Reverse Words in a String

你的名字 2022-08-07 10:44 4阅读 0赞

题目：  
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代码要简洁地多！