LeetCode-151.反转字符串中的单词

双指针#

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

s 包含英文大小写字母、数字和空格 ' '

s 中 至少存在一个 单词

示例 1：

1
输入：s = "the sky is blue"
2
输出："blue is sky the"

示例 2：

1
输入：s = "  hello world  "
2
输出："world hello"
3
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
输入：s = "a good   example"
2
输出："example good a"
3
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

1.自己的方法(调用API)

原来这种题不让调用啊🤔，我还在想这就是中等题吗…

1
func reverseWords(s string) string {
2
    words := strings.Fields(s)
3

4
    left, right := 0, len(words)-1
5
    for left < right {
6
        words[left], words[right] = words[right], words[left]
7
        left++
8
        right--
9
    }
10

11
    return strings.Join(words, " ")
12
}

2.正确的方法(双指针)

思路:1. 移除多余空格 -> 2. 翻转整个字节切片 -> 3. 翻转每个单词

疑惑点:翻转每个单词，依赖后面的空格，因此最后一个单词需要额外的边界处理

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

4
    fast, slow := 0, 0
5
    for ; fast<len(b); fast++ {
6
        if b[fast] != ' ' {
7
            if slow != 0 {
8
                b[slow] = ' '
9
                slow++
10
            }
11
            for fast<len(b) && b[fast] != ' ' {
12
                b[slow] = b[fast]
13
                fast++
14
                slow++
15
            }
16
        }
17
    }
18

19
    b = b[:slow]
20
    reverse(b)
21

22
    start := 0
23
    for i := 0; i <= len(b); i++ {
24
        if i == len(b) || b[i] == ' '{
25
            reverse(b[start:i])
26
            start = i + 1
27
        }
28
    }
29
    return string(b)
30
}
31

32
func reverse(s []byte)  {
33
    left := 0
34
    right := len(s)-1
35
    for left < right{
36
        s[left], s[right]= s[right], s[left]
37
        left++
38
        right--
39
    }
40
}