Tuesday, November 25, 2014

[LeetCode] Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.


思路:


细节实现题。注意word的定义为前后有分隔的一段连续非空格字符。分隔可以是空格,也可以是字符串的前后边界。从后向前扫,根据空格逐个记录word,并反转append到结果中。

 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
class Solution {
public:
    void reverseWords(string &s) {
        if(s.empty()) return;
        string ret, word;
        
        for(int i=s.size()-1; i>=0; i--) {
            if(isspace(s[i])) {
                if(i<s.size()-1 && !isspace(s[i+1])) {
                    reverse(word.begin(),word.end());
                    ret.append(word+" ");
                    word.clear();
                }
            }
            else {
                word.push_back(s[i]);
            }
        }
        
        if(!isspace(s[0])) {
            reverse(word.begin(),word.end());
            ret.append(word);
        }
        else if(!ret.empty()) {
            ret.pop_back();
        }
            
        s = ret;
    }
};


一遍扫描的解法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    void reverseWords(string &s) {
        string ret;
        int j = s.size();
        for(int i=s.size()-1; i>=0; i--) {
            if(s[i]==' ')
                j = i;
            else if(i==0 || s[i-1]==' ') {
                if(!ret.empty()) ret.append(" ");
                ret.append(s.substr(i, j-i));
            }
        }
        s = ret;
    }
};

8 comments:

  1. C++ Program to Reverse a Strings

    Reverse a String means reverse the position of all character of String. You can use swapping concept to reverse any string in c++.

    ReplyDelete
    Replies
    1. You made a silly comment on a code expert's blog, bro.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. I think what he means might be, there is in place solution, but only for c/c++.

      Delete
  2. Reverse string and reverse words in a string are completely different concepts.

    ReplyDelete
  3. This solution is clean and dense, thanks for sharing.

    ReplyDelete
  4. 方法一注释:
    line9 //==找到word的左端边界. 因为是从后往前扫,所以i+1在i左边。
    line11 //==添加到result串右侧。由于从原串的右往左扫, 所以自动翻转了整个原串words的次序!
    line20 //==如果源串头没有空格。是在处理源串第一个word,因为第9行的if条件,如果源串第一个word左侧无空格,第10行的翻转没执行
    line21 //==补足源串是“firstWord_” 的情形,翻转它
    line24 //==源串是“_firstWord_” 情形下,result串要去掉最后一个空格。

    ReplyDelete
  5. 可惜您没有reverse IN PLACE 的版本!!!
    虽然我自己写了一个,但实在不敢贴在这里 :)

    ReplyDelete