leetcode 557. Reverse Words in a String III（字符串中单词逆序III）

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Example 2:

Input: s = “God Ding”
Output: “doG gniD”

以空格分割单词，返回每个单词逆序之后的字符串。

思路：

方法1：
先用split分割单词，每个单词利用StringBuilder中的逆序函数进行逆序，
再拼接起来即可。
能通过，但是时间排名比较偏后。

public String reverseWords(String s) {
    String[] words = s.split(" ");
    
    for(int i = 0; i < words.length; i++)
        words[i] = (new StringBuilder(words[i])).reverse().toString();
    
    return String.join(" ", words);
}
1
2
3
4
5
6
7
8

方法2：
双指针

不需要用split分割单词，
用尾指针不断移动，指向空格 或者 字符串终点时 说明到达一个单词的结尾。
逆序就是首尾字母互换，用双指针一个指头一个指尾。
字符串直接是不能操作的，先转为char数组。

public String reverseWords(String s) {
    int n = s.length();
    char[] words = s.toCharArray();
    int start = 0;
    
    for(int end = 0; end <= n; end++) {
        if(end == n || words[end] == ' ') {
            reverse(start, end-1,  words);
            start = end + 1;
        }           
    }
    
    return new String(words);
}

void reverse(int start, int end, char[] arr) {
    while(start < end) {
        char tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
        start ++;
        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