lintcode翻转字符串


翻转字符串 

给定一个字符串,逐个翻转字符串中的每个单词。

说明

  • 单词的构成:无空格字母构成一个单词
  • 输入字符串是否包括前导或者尾随空格?可以包括,但是反转后的字符不能包括
  • 如何处理两个单词间的多个空格?在反转字符串中间空格减少到只含一个

样例
个题要求的是翻转单词,不是每个字母都翻转,下面方法一是用了额外空间的。方法二没用额外空间,空间复杂度为O(1)

方法一:

class Solution { 
    public: /* * @param s: A string * @return: A string */ 
    string reverseWords(string &s) { // write your code here 
        string line,word; 
        int i=s.size()-1; 
        int start,end; //start记录每个单词头,end记录每个单词尾
        for(;i>=0;i--)//每翻转一个单词记录一次 
        {  
           end=i,start=i; 
           while(s[i]==' '&&i>=0) 
           { 
               i--; 
               start--; 
               end--; 
           } 
           while(s[i]!=' '&&i>=0) 
           { 
               start--; 
                i--;
           } 
            word.resize(0);//每个单词记录前清空word 
           while(start+1<=end) 
           {
               word=word+s[start+1];
               start++; 
            } 
            if(i==0) { 
                line=line+word; 
             } 
            else 
            line=line+word+' '; 
            
        } 
        return line; 
    } 
};
方法二:

别人的方法,借鉴一下。地址http://www.cnblogs.com/grandyang/p/4606676.html

先整个字符串整体翻转一次,然后再分别翻转每一个单词(或者先分别翻转每一个单词,然后再整个字符串整体翻转一次),此时就能得到我们需要的结果了。那么这里我们需要定义一些变量来辅助我们解题,storeIndex表示当前存储到的位置,n为字符串的长度。我们先给整个字符串反转一下,然后我们开始循环,遇到空格直接跳过,如果是非空格字符,我们此时看storeIndex是否为0,为0的话表示第一个单词,不用增加空格;如果不为0,说明不是第一个单词,需要在单词中间加一个空格,然后我们要找到下一个单词的结束位置我们用一个while循环来找下一个为空格的位置,在此过程中继续覆盖原字符串,找到结束位置了,下面就来翻转这个单词,然后更新i为结尾位置,最后遍历结束,我们剪裁原字符串到storeIndex位置,就可以得到我们需要的结果,代码如下:

class Solution {
public:
    void reverseWords(string &s) {
        int storeIndex = 0, n = s.size();//storeIndex为翻转后的下标
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; ++i) {//每翻转一个单词循环一次
            if (s[i] != ' ') {
                if (storeIndex != 0) s[storeIndex++] = ' ';//每个单词间加上空格
                int j = i;
                while (j < n && s[j] != ' ') 
                s[storeIndex++] = s[j++];//覆盖掉的数据要么是空格要么是记录过得
                reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
                i = j;
            }
        }
        s.resize(storeIndex);//重新分配大小
    }
};
相关文章
相关标签/搜索