GuilinDev

Lc0151

05 August 2008

151 - Reverse Words in a String

原题概述

Given an input string, reverse the string word by word.

Example:

1
2

Input: "the sky is blue",
Output: "blue is sky the".

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up: For C programmers, try to solve it in-place in O(1) space.

题意和分析

只是翻转单词间的顺序，单词自身的字符是不翻转的，可以先翻转整个字符串，然后再翻转每一个单词（当然也可以先分别翻转每一个单词，然后再整个字符串翻转一遍），遇到空格就知道是否一个单词结束了。

如果用stack呢？用空格区分单词，最后一个单词应该怎么处理。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class Solution {
    public String reverseWords(String s) {
        int storeIndex = 0, n = s.length();
        StringBuilder sb = new StringBuilder(s).reverse();//先翻转整个字符串一次
        for (int i = 0; i < n; i++) {
            if (sb.charAt(i) != ' ') {
                if (storeIndex != 0) sb.setCharAt(storeIndex++, ' ');
                int j = i;
                while (j < n && sb.charAt(j) != ' ') sb.setCharAt(storeIndex++, sb.charAt(j++));
                String t = new StringBuilder(sb.substring(storeIndex - (j - i), storeIndex)).reverse().toString();
                sb.replace(storeIndex - (j - i), storeIndex, t);
                i = j;
            }
        }
        sb.setLength(storeIndex);
        return sb.toString();
    }
}

不用StringBuilder

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

public class Solution {

    public String reverseWords(String s) {
        if (s == null) return null;

        char[] a = s.toCharArray();
        int n = a.length;

        // 第一步，倒转整个字符串
        reverse(a, 0, n - 1);
        // 第二步，倒转每个单词
        reverseWords(a, n);
        // 第三步，清除多余的空格
        return cleanSpaces(a, n);
    }

    void reverseWords(char[] a, int n) {
        int i = 0, j = 0;

        while (i < n) {
            while (i < j || i < n && a[i] == ' ') i++; // skip spaces
            while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
            reverse(a, i, j - 1);                      // reverse the word
        }
    }

    // trim leading, trailing and multiple spaces
    String cleanSpaces(char[] a, int n) {
        int i = 0, j = 0;

        while (j < n) {
            while (j < n && a[j] == ' ') j++;             // skip spaces
            while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
            while (j < n && a[j] == ' ') j++;             // skip spaces
            if (j < n) a[i++] = ' ';                      // keep only one space
        }

        return new String(a).substring(0, i);
    }

    // reverse a[] from a[i] to a[j]
    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char t = a[i];
            a[i++] = a[j];
            a[j--] = t;
        }
    }

}

用split来做

1
2
3
4
5
6
7
8
9
10
11

public class Solution {

    public String reverseWords(String s) {
        String result = "";
        String[] words = s.trim().split("\\s+");
        for (int i = words.length - 1; i > 0; i--) {
            result += words[i] + " ";
        }
        return result + words[0];//最后加上words[0]，因为上面的循环没有加否则多了个空格
    }
}

用Java8的join方法直接拼接字符串

1
2
3
4
5
6
7

public class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");//用空格符来分隔每一个单词，而不是用正则
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}
This site is open source. Improve this page.