难度简单469
给定一个字符串
s
,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 1:
输入:s = "Let's take LeetCode contest" 输出:"s'teL ekat edoCteeL tsetnoc"示例 2:
输入: s = "God Ding" 输出:"doG gniD"提示:
1 <= s.length <= 5 * 104
s
包含可打印的 ASCII 字符。s
不包含任何开头或结尾空格。s
里 至少 有一个词。s
中的所有单词都用一个空格隔开。
思路:
时间复杂度:O(N)
空间复杂度:方法1 O(N),方法2 O(1)
- // 方法1:空间复杂度O(N)
- // 先根据空格将s拆分为字符串数组
- // 字符串数组中的元素交换位置:字符串是常量不能随意修改,所以要再转化为[]byte数组后才能进行下标操作
- // 将交换位置后的字符串存入res字符串数组中,并对其进行空格拼接
- func reverseWords(s string) string {
- strArr := strings.Split(s, " ")
- res := make([]string, 0)
- for _, ss := range strArr {
- byteSs := []byte(ss)
- for l, r := 0, len(byteSs)-1; l < r; {
- byteSs[l], byteSs[r] = byteSs[r], byteSs[l]
- l++
- r--
- }
- res = append(res, string(byteSs))
- }
- return strings.Join(res, " ")
- }
-
- // 方法2 原地修改:空间复杂度O(1)
- func reverseWords(s string) string {
- // byteS := []byte(s)
- reverseString := func(bs []byte) {
- for left, right := 0, len(bs) - 1; left < right; {
- bs[left], bs[right] = bs[right], bs[left]
- left++
- right--
- }
- }
-
- byteS := []byte(s)
- for i, j := 0, 0; i < len(byteS); i = j {
- for j < len(byteS) && s[j] != ' ' {
- j++
- }
-
- reverseString(byteS[i:j])
- j++ // 跳到下一个单词起点
- }
-
- return string(byteS)
- }