LeetCode-151 翻转字符串里的单词

段连洁 -

LeetCode 翻转字符串里的单词

Difficulty: 中等

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

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

Solution

这道题算是反正字符串 和 反转字符串中的单词进阶班, 主要是最后的单词去除多余空格比较麻烦

  1. 反转字符串比较简单, 用头尾指针交互元素即可
  2. 反转单词则根据空格判断出单词的范围, 然后再对已经反转的字符串 指定范围再次反转即可得到, 也就是 负负得正 的感觉
  3. 最麻烦的就是去除多余空格, 这个肯定不能原地处理了, 因为很多case中的结果并不是 步骤2字符串 的一部分.

注意: 边界情况 头尾不能有空格, 且遍历字符串时最后一个字符不为 ' ' 的情况

Language: C++

​class Solution {
public:
    string reverseWords(string s) {
        if (s.empty()) return s;
        int l = s.length() - 1;
        // 1. reverse all
        reverseStr(s,0,l);

        // 2. reverse word
        int pre = 0;
        for (int i = 0; i<= l;i++) {
            if (s[pre] == ' ') {
                pre++;
            } else if (s[i] == ' ') {
                reverseStr(s, pre, i-1);
                pre = i+1;
            } else if (i == l) {
                reverseStr(s, pre, i);
            }
        }
        // 3. trim extra empty
        int begin = 0;
        while (begin <= l) {// trim head
            if(s[begin] != ' '){
                break;
            }
            begin++;
        }

        int end = l;
        while (end >= 0) {// trim tail
            if(s[end] != ' '){
                break;
            }
            end--;
        }
        
        pre = begin;
        string ans = "";
        bool firstAdd = false;
        for (int i = begin;i <= end;i++) {
            if (s[pre] == ' ') {
                pre++;
            } else if (s[i] == ' ') {
                if (!firstAdd) {
                    firstAdd = true;
                } else {
                    ans.append(" ");
                }
                ans.append(s.substr(pre,i-pre));
                pre = i+1;
            } else if (i == end) {
                if (!firstAdd) {
                    firstAdd = true;
                } else {
                    ans.append(" ");
                }
                ans.append(s.substr(pre,i-pre + 1));
            }
        }
        return ans;
    }

    /// 反转指定范围内的字符串
    void reverseStr(string &s,int lo, int hi){
        while (lo < hi) {
            s[lo] = s[lo] ^ s[hi];
            s[hi] = s[lo] ^ s[hi];
            s[lo] = s[lo] ^ s[hi];
            lo++;
            hi--;
        }
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了98.43%的用户
内存消耗 :10.6 MB, 在所有 C++ 提交中击败了54.29%的用户

发现不执行 去头去尾 反而变慢了很多

class Solution {
public:
    string reverseWords(string s) {
        if (s.empty()) return s;
        unsigned long l = s.length() - 1;
        // 1. reverse all
        reverseStr(s,0,l);
        cout << "*" << s  << "*" << endl;
        // 2. reverse word
        int pre = 0;
        for (int i = 0; i<= l;i++) {
            if (s[pre] == ' ') {
                pre++;
            } else if (s[i] == ' ') {
                reverseStr(s, pre, i-1);
                pre = i+1;
            } else if (i == l) {
                reverseStr(s, pre, i);
            }
        }
        // 3. trim extra empty
        l = s.length() - 1;
        pre = 0;
        string ans = "";
        bool firstAdd = false;
        for (int i =0;i <= l;i++) {
            if (s[pre] == ' ') {
                pre++;
            } else if (s[i] == ' ') {
                if (!firstAdd) {
                    firstAdd = true;
                } else {
                    ans.append(" ");
                }
                ans.append(s.substr(pre,i-pre));
                pre = i+1;
            } else if (i == l) {
                if (!firstAdd) {
                    firstAdd = true;
                } else {
                    ans.append(" ");
                }
                ans.append(s.substr(pre,i-pre + 1));
            }
        }
        cout << ans << endl;
        return ans;
    }
    
    void reverseStr(string &s,unsigned long lo, unsigned long hi){
        while (lo < hi) {
            s[lo] = s[lo] ^ s[hi];
            s[hi] = s[lo] ^ s[hi];
            s[lo] = s[lo] ^ s[hi];
            lo++;
            hi--;
        }
    }
};

执行用时 :16 ms, 在所有 C++ 提交中击败了33.68%的用户
内存消耗 :10.5 MB, 在所有 C++ 提交中击败了56.39%的用户