题目描述(中等难度)

将字符串的每个单词反过来,单词内部不需要逆转,注意可能会有多余的空格。

解法一

题目很直观,做法也会很直观,哈哈。遍历原字符串,遇到字母就加到一个 temp 变量中,遇到空格,如果 temp 变量不为空,就把 temp 组成的单词加到一个栈中,然后清空 temp 继续遍历。

最后,将栈中的每个单词依次拿出来拼接即可。

有一个技巧可以用,就是最后一个单词后边可能没有空格,为了统一,我们可以人为的在字符串后边加入一个空格。

public String reverseWords(String s) {
    Stack<String> stack = new Stack<>();
    StringBuilder temp = new StringBuilder();
    s += " ";
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ') {
            if (temp.length() != 0) {
                stack.push(temp.toString());
                temp = new StringBuilder();
            }
        } else {
            temp.append(s.charAt(i));
        }
    }
    if (stack.isEmpty()) {
        return "";
    }
    StringBuilder res = new StringBuilder();
    res.append(stack.pop());
    while (!stack.isEmpty()) {
        res.append(" ");
        res.append(stack.pop());
    }
    return res.toString();
}

解法二

可以看下题目中的 Follow up

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

如果用 C 语言,试着不用额外空间解决这个问题。

我们一直用的是 java,而 java 中的 String 变量是不可更改的,如果对它修改其实又会去重新创建新的内存空间。

而 C 语言不同,C 语言中的 string 本质上其实是 char 数组,所以我们可以在给定的 string 上直接进行修改而不使用额外空间。

为了曲线救国,继续用 java 实现,我们先将 String 转为 char 数组,所有的操作都在 char 数组上进行。

 char[] a = s.toCharArray();

至于算法的话,参考了 这里-no-split(-)-no-StringBuilder)。

主要是三个步骤即可。

  1. 原地逆转 char 数组,这会导致每个单词内部也被逆转,接下来进行第二步
  2. 原地逆转每个单词
  3. 去除多余的空格

具体代码的话就直接从 这里-no-split(-)-no-StringBuilder) 粘贴过来了,写的很简洁。几个封装的函数,关键就是去解决怎么原地完成。

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

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

    // step 1. reverse the whole string
    reverse(a, 0, n - 1);
    // step 2. reverse each word
    reverseWords(a, n);
    // step 3. clean up spaces
    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;
    }
}

一开始没有 get 到题目要求空间复杂度为 O(1) 的想法,后来在 discuss 中才突然明白。

results matching ""

    No results matching ""