【MEDIUM】Reverse Words in a String II

发布于: 2018-12-24 22:13
阅读: 68
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/reverse-words-in-a-string-ii/

Given an input string , reverse the string word by word.

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note:

  • A word is defined as a sequence of non-space characters.
  • The input string does not contain leading or trailing spaces.
  • The words are always separated by a single space.

Follow up:

  • Could you do it in-place without allocating extra space?

分析过程

  • 输入:字母和空格组成的字符串
  • 输出:反转字符串内容,但单词内容不反转
  • 思路:将整个字符串翻转一遍,然后再次翻转每个单词

解决方法

class Solution {
public:
    void reverse(vector<char>& str, int begin, int end) {
        if (end <= begin) {
            return;
        }
        
        int low = begin, high = end;
        while (low < high) {
            char tmp = str[low];
            str[low] = str[high];
            str[high] = tmp;
            
            ++low;
            --high;
        }
    }
    
    void reverseWords(vector<char>& str) {
        int len = (int)str.size();
        if (len <= 0) {
            return;
        }
        
        // 先把所有字符翻转一遍
        reverse(str, 0, len - 1);
        
        // 然后开始扫描空格
        int begin = 0;
        for (int i = 0; i < len; i++) {
            // 扫到空格以后,逆转 begin 到 i
            if (str[i] == ' ') {
                reverse(str, begin, i - 1);
                begin = i + 1;
            }
        }
        
        // 翻转最后一个单词
        reverse(str, begin, len - 1);
    }
};

Thanks for reading.

All the best wishes for you! 💕