LeetCode151-翻转字符串里的单词

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/reverse-words-in-a-string/

中文链接：https://leetcode-cn.com/problems/reverse-words-in-a-string/

题目详述

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

示例: 

1
2
输入: "the sky is blue",
输出: "blue is sky the".

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

题目详解

这题的难点在于可能连续存在多个空格，着重点在于处理空格。如果不存在多余的空格，可以采取“整体反转 + 局部反转”的方式来完成单词的反转。

方法一：

  • 每次调用 replaceAll 方法将连续两个空格转换成一个空格，最终字符串中不存在连续两个空格。
  • 然后调用 split 方法进行分割。
  • 最后从后往前拼成一个字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00151 {

    public String reverseWords(String s) {
        while (s.contains("  ")) {
            s = s.replaceAll("  ", " ");
        }
        String[] strings = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (int i = strings.length - 1; i >= 0; --i) {
            if (first) {
                sb.append(strings[i]);
                first = false;
            } else {
                sb.append(' ').append(strings[i]);
            }
        }
        return sb.toString();
    }
}

方法二：

  • 从后往前遍历字符串，自己分割出一个个单词。
  • 把单词拼接成字符串，注意处理最后的空格。
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
public class LeetCode_00151 {

    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        int i = chars.length - 1;
        while (i >= 0) {
            while (i >= 0 && chars[i] == ' ') {
                --i;
            }
            if (i >= 0) {
                int j = i;
                while (i >= 0 && chars[i] != ' ') {
                    --i;
                }
                sb.append(chars, i + 1, j - i).append(' ');
                --i;
            }
        }
        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }
        return sb.toString();
    }
}