算法力扣刷题记录二十三【151.翻转字符串里的单词】

前言

字符串篇，继续。
记录二十三【151.翻转字符串里的单词】

–

一、题目阅读

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词 顺序颠倒且单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

进阶：

如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 *原地* 解法。

二、尝试实现

思路

（1）对参数s应该以空格为分隔符，分割一个一个单词。
（2）流对象能够忽略空格或‘\n’，虽然读取，但是能够忽略。

用stringstream可以完成以空格分割和忽略读取到的空格。

代码实现（测试通过）

class Solution {
public:
    string reverseWords(string s) {
        string result;	//返回值
        stringstream ss(s);	//处理字符串的流对象定义。
        string str;
        while(ss>>str){	//用>>运算符可以忽略空格，以空格为分隔符
            if(result.empty()){
                result.insert(0,str);
            }else{
                result.insert(0,str+' ');	//在新string
            }  
        }
        return result;
    }
};

进阶

在原有字符串中进行解决：

进阶思路

结合记录二十二的思路，在原有string s的后面扩容，把新倒序的单词续到原有字符串的后面。最后再把前面size长度删掉，只取size之后的。

思路示意

（1）首先不能覆盖填充，因为单词不能改变，所以覆盖填充会改变原有的单词。所以就把倒序操作放到整个size的后面。
（2）扩容多大区间？

统计多少个字母；假设count个字母；
统计一共多少个单词。假设有n个单词，需要n-1个空格。
所以扩容count+n-1。在原有size的后面。
总结：s.resize(size+count+n-1);

（3）接下来，翻转单词顺序。

一个指针i从s[size-1]倒着往前找单词，直到s[i] != ’ '。i不再是空格；
单词内的字母没有倒序，所以得找这个单词的头。用指针j=i-1开始，往前找，直到s[j] == ’ '等于空格。s[j+1]~s[i]之间是一个单词。
用一个指针k记录扩容后面的位置，要把“s[j+1]~s[i]”这个单词放在哪个位置？k初始是size。从s[size]开始。
空格处理：
- 如果是倒数第一个单词，那么前面不需要有空格；如果不是倒数第一个单词，就要有空格。

代码实现（测试通过）

可以查看注释解释

class Solution {
public:
        string reverseWords(string s) {
        int size = s.size();
        int count = 0;  //统计有多少个字母
        int num = 0;    //统计多少个单词
        for(int i = 0;i < size;i++){  
            if(s[i] != ' '){	//挨个遍历原来的size，不是空格时，count可以++
                count++;
                if(i+1 < size && s[i+1]==' ' ){	//如果下一位是空格，说明是一个单词，所以num++
                    num++;
                }else if(i == size-1){	//如果s[size-1]不是空格，最后一个单词也要加上。
                    num++;
                }
            }
        }

        s.resize(size+count+num-1);//扩容
        //在扩容的区间开始翻转单词顺序
        int k = size;
        int phase = 0;
        //倒着往前找
        for(int i =size-1;i >=0;){
            if(s[i] != ' '){	//遇到一个单词的末尾字母
                int j = i-1;
                int subchar = 1;
                phase++;		//记录当前翻转的第几个单词
                for(j;j >=0;j--){	//找这个单词多长，for结束后s[j+1]是这个单词的首字母
                    if(s[j] == ' '){
                        break;
                    }
                    subchar++;	//记录单词多长
                }
                if(phase != 1){	//如果不是倒数第一个单词，在后面放单词之前先加一个空格。
                    s[k++] = ' ';
                }
                for(int m = 0;m < subchar;m++){	//单词字母没有倒转，所以正向的顺序把字母放置好。
                    s[k++] = s[j+m+1];
                }
                i = j;
                
            }
            i--;
        }
        s.erase(0,size);	//最后删除从0开始，长度为size的部分。把原有部分删除。
        return s;
    
    }
};

总结：两种方法都解决了。这种扩容可以认为是原地操作。

三、代码随想录学习

学习内容

主要看思路区别和实现区别：
（1）用split库函数，分割string s , 再用一个新字符串。C++里面没有split的函数。要么就是C风格的strtok函数，在< cstring >中，原来的string.h。
（2）因为想到reverse翻转会直接把字母翻转，就没再考虑；其实可以reverse整个string s，再把每个单词reverse回来。
（3）处理空格：多余的空格要删掉，如果不是第一个单词，前面还要留一个空格。（删除空格，也是删除元素，string可以像数组一样操作，所以用双指针法）

代码实现

class Solution {
public:
void phaseReverse(string& s,int start ,int end){	//库函数reverse使用类型iterator。
            if(start > s.size() || end < 0){
                return;
            }
            for(int i = start,j = end-1;i < j;i++,j--){ //左闭右开
                swap(s[i] ,s[j]);
            }
        }
    string reverseWords(string s) {
        //删除空格
        int fast = 0;
        int slow = 0;
        for(;fast < s.size();fast++){
            if(s[fast] != ' '){		//当遇到不该删的字符。如果没有这个判断，单词之间的空格没有删掉。
                if( slow != 0){
                    s[slow++] = ' ';//先给空格再slow++
                }
                while(fast < s.size() && s[fast] != ' '){	//必须有 < s.size() 判断，没有会越界。
                    s[slow] = s[fast];
                    fast++;
                    slow++;
                }
            }
        }

        s.resize(slow);
        reverse(s.begin(),s.end());
        //在翻转每个单词
        for(int i = 0,j = 0;j <= s.size();j++){	//因为phaseReverse左闭右开，所以j <= ，带等号。
            if(s[j] == ' ' || j == s.size()){
                phaseReverse(s,i,j);
                i = j+1;
            }
        }
        return s;
    }
};