文章 224
评论 6
浏览 200771
String - 151. Reverse Words in a String

String - 151. Reverse Words in a String

151. Reverse Words in a String

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

Example 1:

Input: "the sky is blue"
**Output: **"blue is sky the"

Example 2:

Input: "  hello world!  "
**Output: **"world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
**Output: **"example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

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.

思路:

核心思路就是找到两个空格之间的单词,然后生成这个新单词。正则表达式消耗了一些时间,用递归之后运行时间降低了不少。

代码:

java:

class Solution {

    /*public String reverseWords(String s) {
        if (s == null || s.length() == 0) return "";
        
        StringBuilder sb = new StringBuilder();
        String[] words = s.trim().split("\\s+");
        for (int i = words.length - 1; i >= 0; i--)
            sb.append(words[i] + " ");
        return sb.toString().trim();
    }*/

    // 递归
    public String reverseWords(String s) {
        return reverse(0,s).toString();
    } 
    
    private StringBuilder reverse(int index, String s) {
        // 1.找到第一个非空格.
        while (index < s.length() && s.charAt(index) == ' ') index++;
        
        // 2.后面全是空格,就返回一个空对象
        if(index == s.length()) return new StringBuilder();
        
        // 3.找到下一个空格.
        int start = index;
        index = s.indexOf(' ', start);
        
        // 4.后面没有空格,就返回后面的字符串
        if (index == -1) return new StringBuilder(s.substring(start));
        
        // 5.后面还有空格,就继续递归
调用
        StringBuilder remainStr = reverse(index + 1, s);
        
        // 根据返回的sb对象,返回给上一层调用
        return remainStr.length() == 0 ?
        
            // 如果StirngBuilder长度为0,就说明后面全是空格,直接返回这一层调用的这个word
            new StringBuilder(s.substring(start, index)):
        
            // 如果StringBuilder长度不为零,就说明后面要么是原字符串最后一个单词,要么是下层调用返回的StringBuilder,
            // 就加空格再加上本层调用的单词,然后继续返回给上层。
            remainStr.append(" ").append(s.substring(start, index));
    }
}

标题:String - 151. Reverse Words in a String
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/06/28/1561732310114.html

Nothing just happens, it's all part of a plan.

取消