[数据结构与算法]线性空间复杂度解LeetCode 151. 翻转字符串里的单词

线性空间复杂度解LeetCode 151. 翻转字符串里的单词

我的思路是先用原地算法，把多余的空格删去。再用原地转置法转置有效数组。

1. O(1)空间复杂度删除多余空格
   用指针k记录当前扫描过的字符中，最后一个有效字符应该放置新数组的下标。具体代码如下：

while(i < n){
    while (i < n and s[i] == ' '){
        i++;
    }
    while (i < n and s[i] != ' '){
        s[k++] = s[i++];
    }
    s[k++] = s[i++]; // 空格            
}

2. 原地转置
   假设一个字符串由两个字符串A和B组成,即s = “AB”，那么如果要将s变成 ss = “BA”，则需要先将A转置，B转置，最后再将整个字符串转置就可以得到ss。
   这个想法来自于矩阵的逆运算公式:

同理对于“ABCDE”也可以先对A、B、C、D、E先转置，再对整体转置就可以得到我们想要的字符串。
具体代码如下：

class Solution {
public:
    void reverse(string &s,int left,int right){
        while(left<right){
            int t = s[left];
            s[left] = s[right];
            s[right] = t;
            left++;
            right--;
        }
    }
    string reverseWords(string s) {
        // 用O(1)的空间复杂度
        // 原地移动s
        int n = s.length();
        int k = 0;
        int i = 0;
        while(i < n){
            while (i < n and s[i] == ' '){
                i++;
            }
            int left = k;
            while (i < n and s[i] != ' '){
                s[k++] = s[i++];
            }
            reverse(s,left,k-1); // 分别reverse 子单词
            s[k++] = s[i++]; // 空格
            
        }
        if(n>1 && s[n-1]==' ' && s[n-2] == ' '){
            reverse(s,0,k-3);
            return s.substr(0,k-2);
        }else{
            reverse(s,0,k-2);
            return s.substr(0,k-1);
        }
    }
};