algorithm - 有效地反转字符数组中单词(不是字符)的顺序

Question

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

示例输入和输出:

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

应该是O(N) 时间和O(1) 空间(split() 不允许入栈/出栈)。

拼图取自here .

Answer 1

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<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == ' '){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

这在时间上应该是 O(n)，在空间上应该是 O(1)。

编辑:稍微清理一下。

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