557.Reverse_Words_in_a_String_III

Posted on Edited on In Word count in article: 800 Reading time ≈ 1 mins.

557. Reverse Words in a String III

这道题比较简单，就是逆序字符串

  1. 按照空格分割字符串
  2. 字符串逆序
  3. 拼接输出

常规解法

  1. 分割字符串
  2. 倒序遍历字符串
  3. 拼接输出

go 语言实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverseWords(s string) string {
	var res string

	strArr := strings.Split(s, " ")

	for idx, world := range strArr {
		if idx != 0 {
			res += " "
		}
		for i := len(world) - 1; i >= 0 ; i-- {
			res = res + string(world[i])
		}
	}
	return res
}

这样看似逻辑清晰，其实非常耗时，空间占用也大

原地逆序

  1. 分割字符串
  2. 原地逆序，交换字符
  3. 拼接输出

go 语言实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func reverseWords(s string) string {
	strArr := strings.Split(s, " ")
	for i, world := range strArr {
		strArr[i] = revers(world)
	}
	return strings.Join(strArr, " ")
}

func revers(str string) string   {
	bytes := []byte(str)
	i, j := 0, len(bytes) - 1
	for i < j {
		bytes[i], bytes[j] = bytes[j], bytes[i]
		i++
		j--
	}
	return string(bytes)
}

原地逆序时间复杂度为 O(N)，空间复杂度为 O(1)，这样可以大大节省空间