LEETCODE算法: 151. Reverse Words in a String

发表于 更新于 分类于 Waline： 阅读次数：

题目

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

Example 1:

Input: "the sky is blue" Output: "blue is sky the" Example 2:

Input: " hello world! " Output: "world! hello" Explanation: Your reversed string should not contain leading or trailing spaces. Example 3:

Input: "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

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) extra space.

题解

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    void revs(string &t,int l,int r)
    {
         for(int k=l;k<=(l+r)/2;k++)
        {
            swap(t[k],t[l+r-k]);
        }
    }
public:
    string reverseWords(string s) {
        while(s.size()>0&&s[s.size()-1]==' ')
        {
            s.pop_back();
        }
        while(s.size()>0&&s[0]==' ')
        {
            s.erase(0,1);
        }
        if(s.size()==0) return "";
        int i=0;
        while(i+1<s.size())
        {
            if(s[i]==' '&&s[i+1]==' ')
            {
                s.erase(i,1);
            }else{
                i++;
            }
        }
        revs(s,0,s.size()-1);
        int j=0;
        for(i=0;i<s.size();i++)
        {
            if(s[i]==' ')
            {
                revs(s,j,i-1);
                j=i+1;
            }
            if(i==s.size()-1)
            {
                revs(s,j,i);
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//stingstream只能击败8%，超级慢，但是写着简单
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        string ans="",tmp;
        while(ss>>tmp)
        {
            ans.insert(0," "+tmp);
        }
        if(ans!="") ans.erase(0,1);    
        return ans;
    }
};

说明

  • 使用stringstream很快解决问题，但是需要额外空间
  • 如果要O(1)只能用笨办法
  • 小心原始数据为空或全为空格的特殊情况，否则会导致越界