数组与字符串9-翻转字符串里的单词

翻转字符串里的单词

一 题目
来源：leetcode官网
给你一个字符串 s ，逐个翻转字符串中的所有单词 。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

二 解题
先将字符串按空格切割，再过滤掉多余的空格，然后倒叙拼接字符串。

class Solution {
    
    public String reverseWords(String s) {
    
        StringBuilder result = new StringBuilder();
        String format = " %s";
        List<String> tmp = Arrays.asList(s.trim().split(" ")).stream().filter(v -> !v.trim().isBlank()).collect(Collectors.toList());
        result.append(tmp.get(tmp.size()-1));
        for(int i = tmp.size()-2;i>=0;i--){
    
            result.append(String.format(format,tmp.get(i)));
        }
        return result.toString();
    }
}

程序运行效率很低
三 优化
使用两个指针，left指向单词开始，right指向单词结尾，从后往前遍历字符串，将得到的单词加入到StringBuilder中。

class Solution {
    
    public String reverseWords(String s) {
    
        StringBuilder result = new StringBuilder();
        //得到单词结尾
        int right = getLastCharWithoutSpace(s,s.length()-1);
        //得到单词开头
        int left = getFirstChar(s,right);
        while (left>=0 && left<=right){
    
            //先给每个单词都加一个空格，最后去掉结果字符串开头的空格即可
            result.append(' ');
            result.append(s, left, right+1);
            right = getLastCharWithoutSpace(s,left-1);
            if(right>=0){
    
                left = getFirstChar(s,right);
            }
        }
        return result.substring(1);
    }

    //得到单词开头的那个字符的位置
    private int getFirstChar(String tmp,int endIndex){
    
        int left = endIndex;
        while (left>=0){
    
            if(tmp.charAt(left)!= ' '){
    
                left--;
            }else{
    
                break;
            }
        }
        return left+1;
    }

    //得到单词结尾的那个字符位置
    private int getLastCharWithoutSpace(String tmp,int endIndex){
    
        int i = endIndex;
        while (i>=0){
    
            if(tmp.charAt(i)==' '){
    
                i--;
            } else{
    
                break;
            }
        }
        return i;
    }
}