翻转单词顺序 Reverse Words in a String

问题：Given an input string, reverse the string word by word. For example,

Given s = "the sky is blue",
return "blue is sky the".

思路：两轮翻转。第一次整个串彻底反转，第二次逐个单词自身翻转。

输入用例：

输入数据的细节特别重要。开头有空格、结尾有空格、多个空格并列。

class Solution {
public:
    void reverseWords(string &s) {
        int n = s.size();
        if(n == 0)
            return;

        string A = "";
        int idx, left, right;
        right = n-1;
        while(right >= 0 && s[right] == ' ') //去除右侧空格
            right--;
        if(right < 0)
        {
            s = "";
            return;
        }
        idx = 0;
        while(idx <= right && s[idx] == ' ') //去除左侧空格
            idx++;

        while(idx <= right)
        {
            if(s[idx] != ' ' || s[idx-1] != ' ') //拷贝字符和单空格
                A += s[idx];
           idx++;
        }

        n = A.size();
        reverse(A, 0, n-1);

        idx = 0;
        while(idx < n)
        {
            left = idx;
            while(idx < n && A[idx] != ' ')
                idx++;
            right = idx-1;
            reverse(A, left, right);
            idx++; //跳过空格
        }

        s = A;
    }

    void reverse(string &s, int left, int right)
    {
        while(left < right)
            swap(s[left++], s[right--]);
    }
};

下面是jobduOJ的程序，注意：如果要键盘录入一个字符串，其中含有空格，那么最好用gets(str)。

# include<stdio.h>
# include<string.h>
# include<malloc.h>

int reverse(char *str, int left, int right) //添加两个参数来控制翻转位置
{
if(left<0 || left>right || right>strlen(str)-1) //合法性检查
return 0;
char tmp;
while(left<right) //左右游标控制
{
tmp = str[left];
str[left] = str[right];
str[right] = tmp;
left++;
right--;
}
return 1; //学会返回函数执行状态
}

void re_order(char *str)
{
int len = strlen(str);
int i=0,j=0;
while(j<len)
{
while(str[j] != ' ' && str[j] !='\0') //操作检查和合法性检查
{
j++;
}
reverse(str, i, j-1);
j++;
i = j;

}
}

int main()
{
char a[50000];
while(gets(a))
{
reverse(a, 0, strlen(a)-1);
re_order(a);
printf("%s\n",a);
}
return 1;
}