参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

综合考察字符串操作的好题。

# 151.翻转字符串里的单词

力扣题目链接 (opens new window)

给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:
输入: "the sky is blue"
输出: "blue is sky the"

示例 2:
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

# 算法公开课

《代码随想录》算法视频公开课 (opens new window)字符串复杂操作拿捏了! | LeetCode:151.翻转字符串里的单词 (opens new window),相信结合视频再看本篇题解,更有助于大家对本题的理解

# 思路

这道题目可以说是综合考察了字符串的多种操作。

一些同学会使用split库函数,分隔单词,然后定义一个新的string字符串,最后再把单词倒序相加,那么这道题题目就是一道水题了,失去了它的意义。

所以这里我还是提高一下本题的难度:不要使用辅助空间,空间复杂度要求为O(1)。

不能使用辅助空间之后,那么只能在原字符串上下功夫了。

想一下,我们将整个字符串都反转过来,那么单词的顺序指定是倒序了,只不过单词本身也倒序了,那么再把单词反转一下,单词不就正过来了。

所以解题思路如下:

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

举个例子,源字符串为:"the sky is blue "

  • 移除多余空格 : "the sky is blue"
  • 字符串反转:"eulb si yks eht"
  • 单词反转:"blue is sky the"

这样我们就完成了翻转字符串里的单词。

思路很明确了,我们说一说代码的实现细节,就拿移除多余空格来说,一些同学会上来写如下代码:

void removeExtraSpaces(string& s) {
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // 删除字符串最后面的空格
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // 删除字符串最前面的空格
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

逻辑很简单,从前向后遍历,遇到空格了就erase。

如果不仔细琢磨一下erase的时间复杂度,还以为以上的代码是O(n)的时间复杂度呢。

想一下真正的时间复杂度是多少,一个erase本来就是O(n)的操作。

erase操作上面还套了一个for循环,那么以上代码移除冗余空格的代码时间复杂度为O(n^2)。

那么使用双指针法来去移除空格,最后resize(重新设置)一下字符串的大小,就可以做到O(n)的时间复杂度。

//版本一 
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针,慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

有的同学可能发现用erase来移除空格,在leetcode上性能也还行。主要是以下几点;:

  1. leetcode上的测试集里,字符串的长度不够长,如果足够长,性能差距会非常明显。
  2. leetcode的测程序耗时不是很准确的。

版本一的代码是一般的思考过程,就是 先移除字符串前的空格,再移除中间的,再移除后面部分。

不过其实还可以优化,这部分和27.移除元素 (opens new window)的逻辑是一样一样的,本题是移除空格,而 27.移除元素 就是移除元素。

所以代码可以写的很精简,大家可以看 如下 代码 removeExtraSpaces 函数的实现:

// 版本二 
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理,即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词,遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}
1
2
3
4
5
6
7
8
9
10
11
12
13

如果以上代码看不懂,建议先把 27.移除元素 (opens new window)这道题目做了,或者看视频讲解:数组中移除元素并不容易!LeetCode:27. 移除元素 (opens new window)

此时我们已经实现了removeExtraSpaces函数来移除冗余空格。

还要实现反转字符串的功能,支持反转字符串子区间,这个实现我们分别在344.反转字符串 (opens new window)541.反转字符串II (opens new window)里已经讲过了。

代码如下:

// 反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}
1
2
3
4
5
6

整体代码如下:

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转,区间写法:左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理,即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词,遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾,说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转,注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  • 时间复杂度: O(n)
  • 空间复杂度: O(1) 或 O(n),取决于语言中字符串是否可变

# 其他语言版本

# Java:

class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//解法二:创建新字符数组填充。时间复杂度O(n)
class Solution {
    public String reverseWords(String s) {
        //源字符数组
        char[] initialArr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 ",最终末尾的空格不会返回
        int newArrPos = 0;
        //i来进行整体对源字符数组从后往前遍历
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
            //此时i位置是边界或!=空格,先记录当前索引,之后的while用来确定单词的首字母的位置
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //指定区间单词取出(由于i为首字母的前一位,所以这里+1,),取出的每组末尾都带有一个空格
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串没有单词,直接返回空字符串;若是有单词,返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//解法三:双反转+移位,String 的 toCharArray() 方法底层会 new 一个和原字符串相同大小的 char 数组,空间复杂度:O(n)
class Solution {
    /**
     * 思路:
     *	①反转字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍历 " eulb si yks eht",每次先对某个单词进行反转再移位
     *	   这里以第一个单词进行为演示:" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //步骤1:字符串整体反转(此时其中的单词也都反转了)
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //步骤二:二次反转
                    reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转,不反转从后往前遍历一个个填充有问题
                }
                //步骤三:移动操作
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //遍历结束
                    //避免越界情况,例如=> "asdasd df f",不加判断最后就会数组越界
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //参数三:以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    public void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            chars[i] ^= chars[j];
            chars[j] ^= chars[i];
            chars[i] ^= chars[j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * 解法四:时间复杂度 O(n)
 * 参考卡哥 c++ 代码的三步骤:先移除多余空格,再将整个字符串反转,最后把单词逐个反转
 * 有别于解法一 :没有用 StringBuilder  实现,而是对 String 的 char[] 数组操作来实现以上三个步骤
 */
class Solution {
    //用 char[] 来实现 String 的 removeExtraSpaces,reverse 操作
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1.去除首尾以及中间多余空格
        chars = removeExtraSpaces(chars);
        //2.整个字符串反转
        reverse(chars, 0, chars.length - 1);
        //3.单词反转
        reverseEachWord(chars);
        return new String(chars);
    }

    //1.用 快慢指针 去除首尾以及中间多余空格,可参考数组元素移除的题解
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一个单词外,单词末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍历到字符串末尾,就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相当于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //双指针实现指定范围内字符串反转,可参考字符串反转题解
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3.单词反转
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ,是为了让 end 永远指向单词末尾后一个位置,这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# Python:

(版本一)先删除空白,然后整个反转,最后单词反转。 因为字符串是不可变类型,所以反转单词的时候,需要将其转换成列表,然后通过join函数再将其转换成列表,所以空间复杂度不是O(1)

class Solution:
    def reverseWords(self, s: str) -> str:
        # 删除前后空白
        s = s.strip()
        # 反转整个字符串
        s = s[::-1]
        # 将字符串拆分为单词,并反转每个单词
        s = ' '.join(word[::-1] for word in s.split())
        return s

1
2
3
4
5
6
7
8
9
10

(版本二)使用双指针

class Solution:
    def reverseWords(self, s: str) -> str:
        # 将字符串拆分为单词,即转换成列表类型
        words = s.split()

        # 反转单词
        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1

        # 将列表转换成字符串
        return " ".join(words)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Go:

版本一:

func reverseWords(s string) string {
    b := []byte(s)

    // 移除前面、中间、后面存在的多余空格
    slow := 0
    for i := 0; i < len(b); i++ {
        if b[i] != ' ' {
            if slow != 0 {
                b[slow] = ' '
                slow++
            }
            for i < len(b) && b[i] != ' ' { // 复制逻辑
                b[slow] = b[i]
                slow++
                i++
            }
        }
    }
    b = b[0:slow]
    
    // 翻转整个字符串
    reverse(b)
    // 翻转每个单词
    last := 0
    for i := 0; i <= len(b); i++ {
        if i == len(b) || b[i] == ' ' {
            reverse(b[last:i])
            last = i + 1
        }
    }
    return string(b)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

版本二:

import (
	"fmt"
)

func reverseWords(s string) string {
	//1.使用双指针删除冗余的空格
	slowIndex, fastIndex := 0, 0
	b := []byte(s)
	//删除头部冗余空格
	for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' {
		fastIndex++
	}
    //删除单词间冗余空格
	for ; fastIndex < len(b); fastIndex++ {
		if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' {
			continue
		}
		b[slowIndex] = b[fastIndex]
		slowIndex++
	}
	//删除尾部冗余空格
	if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {
		b = b[:slowIndex-1]
	} else {
		b = b[:slowIndex]
	}
	//2.反转整个字符串
	reverse(b)
	//3.反转单个单词  i单词开始位置,j单词结束位置
	i := 0
	for i < len(b) {
		j := i
		for ; j < len(b) && b[j] != ' '; j++ {
		}
		reverse(b[i:j])
		i = j
		i++
	}
	return string(b)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# JavaScript:

/**
 * @param {string} s
 * @return {string}
 */
 var reverseWords = function(s) {
   // 字符串转数组
   const strArr = Array.from(s);
   // 移除多余空格
   removeExtraSpaces(strArr);
   // 翻转
   reverse(strArr, 0, strArr.length - 1);

   let start = 0;

   for(let i = 0; i <= strArr.length; i++) {
     if (strArr[i] === ' ' || i === strArr.length) {
       // 翻转单词
       reverse(strArr, start, i - 1);
       start = i + 1;
     }
   }

   return strArr.join('');
};

// 删除多余空格
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while(fastIndex < strArr.length) {
    // 移除开始位置和重复的空格
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}

// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while(left < right) {
    // 交换
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# TypeScript:

function reverseWords(s: string): string {
    /** Utils **/
    // 删除多余空格, 如'   hello     world   ' => 'hello world'
    function delExtraSpace(arr: string[]): void {
        let left: number = 0,
            right: number = 0,
            length: number = arr.length;
        while (right < length && arr[right] === ' ') {
            right++;
        }
        while (right < length) {
            if (arr[right] === ' ' && arr[right - 1] === ' ') {
                right++;
                continue;
            }
            arr[left++] = arr[right++];
        }
        if (arr[left - 1] === ' ') {
            arr.length = left - 1;
        } else {
            arr.length = left;
        }
    }
    // 翻转字符串,如:'hello' => 'olleh'
    function reverseWords(strArr: string[], start: number, end: number) {
        let temp: string;
        while (start < end) {
            temp = strArr[start];
            strArr[start] = strArr[end];
            strArr[end] = temp;
            start++;
            end--;
        }
    }

    /** Main code **/
    let strArr: string[] = s.split('');
    delExtraSpace(strArr);
    let length: number = strArr.length;
    // 翻转整个字符串
    reverseWords(strArr, 0, length - 1);
    let start: number = 0,
        end: number = 0;
    while (start < length) {
        end = start;
        while (strArr[end] !== ' ' && end < length) {
            end++;
        }
        // 翻转单个单词
        reverseWords(strArr, start, end - 1);
        start = end + 1;
    }
    return strArr.join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# Swift:

func reverseWords(_ s: String) -> String {
    var stringArr = removeSpace(s)
    reverseString(&stringArr, startIndex: 0, endIndex: stringArr.count - 1)
    reverseWord(&stringArr)
    return String(stringArr)
}

/// 1、移除多余的空格(前后所有的空格,中间只留一个空格)
func removeSpace(_ s: String) -> [Character] {
    let ch = Array(s)
    var left = 0
    var right = ch.count - 1
    // 忽略字符串前面的所有空格
    while ch[left] == " " {
        left += 1
    }
    // 忽略字符串后面的所有空格
    while ch[right] == " " {
        right -= 1
    }

    // 接下来就是要处理中间的多余空格
    var lastArr = Array<Character>()
    while left <= right {
        // 准备加到新字符串当中的字符
        let char = ch[left]
        // 新的字符串的最后一个字符;或者原字符串中,准备加到新字符串的那个字符;这两个字符当中,只要有一个不是空格,就可以加到新的字符串当中
        if char != " " || lastArr[lastArr.count - 1] != " "  {
            lastArr.append(char)
        }
      
        left += 1
    }
    return lastArr
}

/// 2、反转整个字符串
func reverseString(_ s: inout [Character], startIndex: Int, endIndex: Int)  {
    var start = startIndex
    var end = endIndex
    while start < end {
        (s[start], s[end]) = (s[end], s[start])
        start += 1
        end -= 1
    }
}

/// 3、再次将字符串里面的单词反转
func reverseWord(_ s: inout [Character]) {
    var start = 0
    var end = 0
    var entry = false

    for i in 0..<s.count {
        if !entry {
            start = i
            entry = true
        }
      
        if entry && s[i] == " " && s[i - 1] != " " {
            end = i - 1
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }

        if entry && (i == s.count - 1) && s[i] != " " {
            end = i
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# Scala:

object Solution {
  def reverseWords(s: String): String = {
    var sb = removeSpace(s) // 移除多余的空格
    reverseString(sb, 0, sb.length - 1) // 翻转字符串
    reverseEachWord(sb)
    sb.mkString
  }

  // 移除多余的空格
  def removeSpace(s: String): Array[Char] = {
    var start = 0
    var end = s.length - 1
    // 移除字符串前面的空格
    while (start < s.length && s(start) == ' ') start += 1
    // 移除字符串后面的空格
    while (end >= 0 && s(end) == ' ') end -= 1
    var sb = "" // String
    // 当start小于等于end的时候,执行添加操作
    while (start <= end) {
      var c = s(start)
      // 当前字符不等于空,sb的最后一个字符不等于空的时候添加到sb
      if (c != ' ' || sb(sb.length - 1) != ' ') {
        sb ++= c.toString
      }
      start += 1 // 指针向右移动
    }
    sb.toArray
  }

  // 翻转字符串
  def reverseString(s: Array[Char], start: Int, end: Int): Unit = {
    var (left, right) = (start, end)
    while (left < right) {
      var tmp = s(left)
      s(left) = s(right)
      s(right) = tmp
      left += 1
      right -= 1
    }
  }

  // 翻转每个单词
  def reverseEachWord(s: Array[Char]): Unit = {
    var i = 0
    while (i < s.length) {
      var j = i + 1
      // 向后迭代寻找每个单词的坐标
      while (j < s.length && s(j) != ' ') j += 1
      reverseString(s, i, j - 1)  // 翻转每个单词
      i = j + 1   // i往后更新
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# PHP:

function reverseWords($s) {
    $this->removeExtraSpaces($s); 
    $this->reverseString($s, 0, strlen($s)-1);
    // 将每个单词反转
    $start = 0; 
    for ($i = 0; $i <= strlen($s); $i++) {
        // 到达空格或者串尾,说明一个单词结束。进行翻转。
        if ($i == strlen($s) || $s[$i] == ' ') { 
            // 翻转,注意是左闭右闭 []的翻转。
            $this->reverseString($s, $start, $i-1);
            // +1: 单词与单词直接有个空格
            $start = $i + 1; 
        }
    }
    return $s;
}

// 移除多余空格
function removeExtraSpaces(&$s){
    $slow = 0;   
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] != ' ') { 
            if ($slow != 0){
                $s[$slow++] = ' ';
            } 
            while ($i < strlen($s) && $s[$i] != ' ') { 
                $s[$slow++] = $s[$i++];
            }
        }
    }
    // 移动覆盖处理,丢弃多余的脏数据。
    $s = substr($s,0,$slow);
    return ;
}

// 翻转字符串
function reverseString(&$s, $start, $end) {
    for ($i = $start, $j = $end; $i < $j; $i++, $j--) {
        $tmp = $s[$i];
        $s[$i] = $s[$j];
        $s[$j] = $tmp;
    }
    return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# Rust:

// 根据C++版本二思路进行实现
// 函数名根据Rust编译器建议由驼峰命名法改为蛇形命名法
impl Solution {
    pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
        while begin < end {
            let temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            begin += 1;
            end -= 1;
        }
}
pub fn remove_extra_spaces(s: &mut Vec<char>) {
        let mut slow: usize = 0;
        let len = s.len();
        // 注意这里不能用for循环,不然在里面那个while循环中对i的递增会失效
        let mut i: usize = 0;
        while i < len {
            if !s[i].is_ascii_whitespace() {
                if slow != 0 {
                    s[slow] = ' ';
                    slow += 1;
                }
                while i < len && !s[i].is_ascii_whitespace() {
                    s[slow] = s[i];
                    slow += 1;
                    i += 1;
                }
            }
            i += 1;
        }
        s.resize(slow, ' ');
    }
    pub fn reverse_words(s: String) -> String {
        let mut s = s.chars().collect::<Vec<char>>();
        Self::remove_extra_spaces(&mut s);
        let len = s.len();
        Self::reverse(&mut s, 0, len - 1);
        let mut start = 0;
        for i in 0..=len {
            if i == len || s[i].is_ascii_whitespace() {
                Self::reverse(&mut s, start, i - 1);
                start = i + 1;
            }
        }
        s.iter().collect::<String>()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# C:

// 翻转字符串中指定范围的字符
void reverse(char* s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

// 删除字符串两端和中间多余的空格
void removeExtraSpace(char* s) {
    int start = 0; // 指向字符串开头的指针
    int end = strlen(s) - 1; // 指向字符串结尾的指针
    while (s[start] == ' ') start++; // 移动指针 start,直到找到第一个非空格字符
    while (s[end] == ' ') end--; // 移动指针 end,直到找到第一个非空格字符
    int slow = 0; // 指向新字符串的下一个写入位置的指针
    for (int i = start; i <= end; i++) { // 遍历整个字符串
        if (s[i] == ' ' && s[i+1] == ' ')  { // 如果当前字符是空格,并且下一个字符也是空格,则跳过
            continue;
        }
        s[slow] = s[i]; // 否则,将当前字符复制到新字符串的 slow 位置
        slow++; // 将 slow 指针向后移动
    }
    s[slow] = '\0'; // 在新字符串的末尾添加一个空字符
}

// 翻转字符串中的单词
char * reverseWords(char * s){
    removeExtraSpace(s); // 先删除字符串两端和中间的多余空格
    reverse(s, 0, strlen(s) - 1); // 翻转整个字符串
    int slow = 0; // 指向每个单词的开头位置的指针
    for (int i = 0; i <= strlen(s); i++) { // 遍历整个字符串
        if (s[i] ==' ' || s[i] == '\0') { // 如果当前字符是空格或空字符,说明一个单词结束了
            reverse(s, slow, i-1); // 翻转单词
            slow = i + 1; // 将 slow 指针指向下一个单词的开头位置
        }
    }
    return s; // 返回处理后的字符串
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# C#

public string ReverseWords(string s) {
    return string.Join(' ', s.Trim().Split(' ',StringSplitOptions.RemoveEmptyEntries).Reverse());
}
1
2
3

上次更新:: 11/30/2023, 10:16:49 AM
@2021-2022 代码随想录 版权所有 粤ICP备19156078号