leetcode 151 翻转字符串里的单词-蒲公英云

leetcode 151 翻转字符串里的单词

前言

题目：151. 翻转字符串里的单词

参考题解：翻转字符串里的单词-力扣官方题解

提交代码

使用栈翻转

使用空格作为分隔符，提取语句中的单词放入栈中。将栈中的单词弹出，连接成语句。从而翻转语句。

class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        stack<string> st;
        string result;
        // 当一句话中的单词全部压栈
        string word;
        while(ss>>word){
            st.push(word);
            st.push(" "); // 压入一个空格
        }
        st.pop();
        // 弹栈到result中
        while(!st.empty()){
            result+=st.top();
            st.pop();
        }
        return result;
    }
};

原空间翻转

除非脑力过剩，要不然不会使用这种方法。不使用附加空间进行翻转，我参看了答案的思路之后，也进行了代码实现。

思路：移除多余空格-将整个字符串反转-将每个单词反转。

class Solution {
public:
    string deleteExtraSpaces(string s){
        // 使用快慢指针删除字符串中的多余空格：[i,j)范围的内容为多余内容
        if(s.empty())
            return s;
        const int len = s.size();
        int i=0,j=0;
        while(j<len){
            if((s[j]!=' ') || (j-1>=0 && s[j-1]!=' ')) // 合法需要保留的字符("word ")：本身不是空格 || 作为分隔符的空格(本身是空格 && 前一个不是空格)
                s[i++] = s[j++]; 
            else{
                j++;
            }
        }
        if(s[i-1]==' ') // 上面过滤出的是(word )*格式。过滤，最后一个可能是空格，单独处理一下
            i--;
        assert(s[0]!=' ' || s[len-1]!=' ');
        if(i!=len)
            s.resize(i);
        return s;
    }
    // string reverseWord(string s, int start, int end){ //[start，end]闭区间翻转
    //     reverse(s.begin()+start,s.begin()+end+1);
    // }
    string reverseWords(string s) {
        if(s.empty())
            return s;
        s = deleteExtraSpaces(s); // 删除多余空格
        reverse(s.begin(),s.end()); // 字符串翻转
        // 翻转单词,[i,j]闭合范围内为一单词
        int i=0,j=0;
        s.push_back(' '); // 统一格式为(word )
        const int len = s.size();
        while(i<len && j<len){
            while(s[j]!=' ') j++;
            reverse(s.begin()+i,s.begin()+j);
            i = j+1;
            j++; 
        }
        s.pop_back(); // 删除最后一个空格
        return s;
    }
};

附录

关于删除字符串之前/之后的空格，我这里保存了一份挺好看的代码。

// trim from start (construct new string)
inline std::string ltrim(const std::string &str){
    std::string s(str);
    s.erase(s.begin(), std::find_if_not<decltype(s.begin()), int(int)>(s.begin(), s.end(),
        std::isspace));
    return s;
    }
// trim from end (construct new string)
inline std::string rtrim(const std::string &str){
    std::string s(str);
    s.erase(std::find_if_not<decltype(s.rbegin()), int(int)>(s.rbegin(), s.rend(),
        std::isspace).base(), s.end());
    return s;
}