[C++]LeetCode: 107 Reverse Words in a String (2014腾讯实习笔试题)

浏览数：26 / 时间：2015年06月08日

题目：

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

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

click to show clarification.

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.

思路：

我们首先要考虑几个特殊情况：

输入空字符串，如何处理
如果字符串前面有空格，或者末尾有空格，怎么处理
如果单词之间不止一个空格，如何处理，我们翻转字符串后，应该单词间只包含一个空格

Answer 1: 利用栈

接下来，看到反转的题目，首先想到的就是利用栈，把每个单词读入后，之后再出栈，加空格，输出。注意的就是如何处理，上面问题的细节。

Attention:

1. ***如何去除前导空格，我们判断存储单词的tmp，如果不为空时，我们才像stack压栈。这样遇到第一个单词的首字母时，我们不会压栈。***

if(s[i] != ' ')    //字符比较 空格是' '
            {
                tmp += s[i];   
            }
            else
            {
                //如果tmp为空，说明还没有添加单词 有前导空格,不需要tag来判断
                if(!tmp.empty())
                {
                    stk.push(tmp);
                    tmp.clear();
                }
            }

2. 我们需要区分两种情况，如果字符串有后导空格，最后一个单词会被压栈，但是如果没有，最后一个单词还保留在tmp中，所以我们需要判断是否压栈。

 //如果字符串末尾没有空格，最后一个单词就还没有push进stk 需要判断
        if(!tmp.empty())
            stk.push(tmp);

3. 我们出栈，输出单词时，需要区分前n-1个单词和最后一个单词，最后一个单词出栈后不加空格。要分开处理。

s.clear();
        while(stk.size() > 1)
        {
            s += stk.top();
            stk.pop();
            s += " ";
        }
        //最后一个单词处理后不加空格 需要单独处理
        if(!stk.empty())
        {
            s += stk.top();
            stk.pop();
        }

4. 比较时，必须类型匹配。字符空格 ‘ ’

if(s[i] != ' ')    //字符比较 空格是' '

这道题难度并不是很大，但是考察面试者的思维严密性，是否能把情况考虑全面。

复杂度：O(N)

AC Code:

class Solution {
public:
    void reverseWords(string &s) {
        if(s.size() == 0) return;
        string tmp;
        stack<string> stk;
      
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] != ' ')    //字符比较 空格是' '
            {
                tmp += s[i];   
            }
            else
            {
                //如果tmp为空，说明还没有添加单词 有前导空格,不需要tag来判断
                if(!tmp.empty())
                {
                    stk.push(tmp);
                    tmp.clear();
                }
            }
        }
        //如果字符串末尾没有空格，最后一个单词就还没有push进stk 需要判断
        if(!tmp.empty())
            stk.push(tmp);
            
        s.clear();
        while(stk.size() > 1)
        {
            s += stk.top();
            stk.pop();
            s += " ";
        }
        //最后一个单词处理后不加空格 需要单独处理
        if(!stk.empty())
        {
            s += stk.top();
            stk.pop();
        }
        return;
    }
};

Answer 2: 不用栈，直接得到result

思路：我们设置一个位置标记pos，用来标记单词首字母的位置。如果存在前导空格，或者单词间存在多个空格，pos会随着坐标移动，始终在空格前一位，直到出现非空格，pos停止前进。我们可以用pos来截取单词。注意，我们依然要考虑最后一个单词的处理，如果有后导空格，依然和前面一样处理，如果没有，我们就需要单独处理.result = s.substr(pos,s.size()-pos)+" "+result;

Attention:

1. 我们在处理第一个单词时，加入了一个空格在后面，最后这个空格就被置为反转后的字符串末尾，最后返回字符串时要去掉。

s = result.substr(0,result.size()-1) ;

2. 只有在当前坐标在pos前面，并且此时为空格时，才添加单词。

 if (s[i] == ' '){
                if (i > pos )
                    result = s.substr(pos,i-pos)+ " " + result ;

3. 我们可以使用这种构造字符串的方式，形成反转。每次把之前得到的字符串放到后面。

result = s.substr(pos,i-pos)+ " " + result ;

4. 注意处理当没有后导空格时，我们要单独计算最后一个单词的长度。

result = s.substr(pos,s.size()-pos)+" "+result;

5. 如果输出是一串空格，没有字符，输出应该是空串。

input: " " ; expected output: ""

6. 空格也是占位的，s.substr(0, -1)返回空串，“”

AC Code:

class Solution {
public:
    void reverseWords(string &s) {
        if(s.size() == 0) return;
        string result;
        int pos = 0;
        
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == ' ')
            {
                if(i > pos)
                {
                    result = s.substr(pos, i-pos) + " " + result;
                }
                pos = i + 1;
            }
            else if(i == s.size()-1)
            {
                result = s.substr(pos, s.size()-pos) + " " + result;
            }
        }
        
        s = result.substr(0, result.size()-1);
    }
};