151. Reverse Words in a String

发表于 | 分类于

每日一题 2019 - 05 - 13

题目：

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

Example 1:

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

Example 2:

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

Example 3:

1
2
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.

解法：

这个题让把给定字符串 s 中的单词全部进行逆序重新排列，但是单词自身的顺序不变，只改变位置顺序，所以使用数据结构栈就可以完成任务，但是在对单词进行提取过程中，需要注意一些点：

  • 提取单词开始，如果是空格则一直跳过，不进行提取
  • 当提取单词过程中遇到空格时候，则单词提取结束
  • 如果到单词结尾，结尾符是空格则要保证提取的字符串少一位

代码：

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
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    string reverseWords(string s) {
        stack<string> now ;
        if(s.size() == 0)
        {
            return s ;
        }
        for(int i = 0 ; i < s.size() ; i ++ )
        {
            if(s[i] == ' ')
            {
                continue ;
            }
            for(int j = i ; j < s.size() ; j ++ )
            {
                if(s[j] != ' ' && j != s.size() - 1)
                {
                    continue ;
                }
                else
                {
                    string temp ;
                    if(j == s.size() - 1 && s[s.size()-1]!= ' ')
                    {
                        temp = s.substr(i,j-i+1);
                    }
                    else
                    {
                         temp = s.substr(i,j-i);   
                    }
                    now.push(temp);
                    i = j ;
                    break ;
                }
            }
        }
        string test ;
        int i = 0 ;
        while(!now.empty())
        {
            if(i == 0)
            {
                test += now.top() ;
                now.pop();
            }
            else
            {
                test += " " ;
                test += now.top();
                now.pop();
            }
            i ++ ;
        }
        return test ;
    }
};
0%
undefined