Huge Lemon的博客

反转字符串中的单词 III

2020-02-10

From LeetCode 557. Reverse Words in a String III

题目描述

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1:

输入: “Let’s take LeetCode contest”
输出: “s’teL ekat edoCteeL tsetnoc”
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

思路

误区

第一眼看上去是反转字符串，而反转字符串的形式有所不同——并不是整体反转，而是单个单词进行反转，所有单词相对位置不变。
(我第一次提交的时候没有注意到，因此有了以下代码)

1
2
3
4
5
6
7
8
9
10
11
char * reverseWords(char * s){
    int len = strlen(s);
    int i;
    char temp;
    for(i=0; i<len/2; i++){
    	temp = s[i];
    	s[i] = s[len-i-1];
    	s[len-i-1] = temp;
	}
	return s;
}

此代码是反转整个字符串，与线性表的反转类似【见就地逆置线性表元素】

输入：”Let’s take LeetCode contest”
输出：“tsetnoc edoCteeL ekat s’teL”
预期：“s’teL ekat edoCteeL tsetnoc”

正确解题思路

  • 记录s的长度len
  • 若s为空或只有一个字符，则直接返回
  • 否则
    • 使用r记录翻转后的字符串，用start指向每一个单词的第一个字母，end指向该单词的最后一个字符（遇到空格或者结束符就停下）
    • 将start到end之间的字符复制到r中

代码

来源：LeetCode - kdurant

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char * reverseWords(char * s){
    int len = strlen(s) + 1, index = 0;

    if(len == 1 || len == 2)
        return s;

    char * r = (char *)malloc(len);
    char *start = s, *end;

    for(int i = 0; i < len; i++, s++){
        if(*s == ' ' || *s == '\0'){
            for(end = s - 1; end >= start; end--){
                r[index++] = *end;
            }
            r[index++] = (*s == ' ') ? ' ' : (*s = '\0');
            start = s + 1;
        }
    }
    return r;
}

时间复杂度$O(n)$, 空间复杂度$O(n)$

Tags: 算法 LeetCode
← 无重复字符的最长子串 有序循环数组查找值 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏