前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >String - 151. Reverse Words in a String

String - 151. Reverse Words in a String

作者头像
ppxai
发布2020-09-23 17:15:08
3680
发布2020-09-23 17:15:08
举报
文章被收录于专栏:皮皮星球

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:

代码语言:javascript
复制
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));
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年06月28日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档