【MEDIUM】Reverse Words in a String II

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

问题

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

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

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

分析过程

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

解决方法

// 翻转字符串的一段
void reverse(char *str, long begin, long end) {
    if (end <= begin) {
        return;
    }
    char *low = str + begin, *high = str + end;
    while (low < high) {
        char tmp = *low;
        *low = *high;
        *high = tmp;
        
        ++low;
        --high;
    }
}

void reverseString(char *str) {
    if (!str) {
        return;
    }
    long len = strlen(str);
    if (len <= 0) {
        return;
    }
    
    // 先把所有字符翻转一遍
    reverse(str, 0, len - 1);
    
    // 然后开始扫描空格
    char begin = 0;
    for (long i = 0; i < len; i++) {
        // 扫到空格以后,逆转 begin 到 i
        if (str[i] == ' ') {
            reverse(str, begin, i - 1);
            begin = i + 1;
        }
    }
    
    // 翻转最后一个单词
    reverse(str, begin, len - 1);
    
    // 不过,如果整个单词没有空格,会被翻过去再翻回来,这种 case 可以再单独优化
}

int main() {
    char str[] = "the sky is blue";
    reverseString(str);
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕