剑指 Offer 58 - I 翻转单词顺序

概述

https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/

https://leetcode.com/problems/reverse-words-in-a-string/

暴力法

解析输入字符串，构造 string vector，之后反向遍历 join 起来即可。

离谱哦，本来索引写错成 i = ws.size() 竟然没报错？

class Solution {
public:
    string reverseWords(string s) {
        vector<string> ws;
        string w;
        for (auto c : s) {
            if (c == ' ') {
                if (w == "") {
                    continue;
                } else {
                    ws.push_back(w);
                    w = "";
                }
            } else {
                w += c;
            }
        }
        if (w != "") ws.push_back(w);
        string ans;
        for (int i = ws.size() - 1; i >= 0; i --) {
            ans += ws[i];
            if (i != 0) ans += " ";
        }
        return ans;
    }
};

O(1) 空间复杂度的原地翻转

先原地翻转整个句子，再翻转每个单词。

由于题目要求我们返回一个符合要求的字符串，所以我们其实还得声明新字符串。

实现的时候注意，调用 back() 前先检查是否为空，不然其是不报错的要注意。

class Solution {
public:
    string reverseWords(string s) {
        reverse(s, 0, s.size() - 1);
        for (int l = 0; l < s.size();) {
            if (s[l] == ' ') {
                l ++;
                continue;
            };
            int r = l;
            for (; r < s.size(); r ++) {
                if (s[r] == ' ') {
                    break;
                }
            }
            r --;
            reverse(s, l, r);
            l = r + 1;
        }
        string ans;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] != ' ') {
                ans.push_back(s[i]);
            } else {
                if (!ans.empty() && ans.back() != ' ') ans.push_back(s[i]);
            }
        }
        if (ans.back() == ' ') ans.pop_back();
        return ans;
    }
    
    void reverse(string& s, int l, int r) {
        while (l < r) {
            swap(s[l++], s[r--]);
        }
    }
};

Links: sword-offer-58-1

未经允许，禁止转载，本文源站链接：https://iamazing.cn/