有效地颠倒字符数组中单词(不是字符)的顺序

给定一个形成单词句子的字符数组,给出一个有效的算法来反转其中单词(而不是字符)的顺序.

示例输入和输出:

>>> reverse_words("this is a string")
'string a is this'

它应该是O(N)时间和O(1)空间(split()并且不允许推入/弹出堆栈).

这个难题来自这里.

C/C++中的解决方案:

void swap(char* str, int i, int j){
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length){
    for(int i=0; i

这应该是O(n)的时间和O(1)的空间.

编辑:清理一下.

字符串上的第一次传递显然是O(n/2)= O(n).第二遍是O(n +所有字的组合长度/ 2)= O(n + n/2)= O(n),这使得这是O(n)算法.