151.反转字符串中的单词

题目描述

给你一个字符串s，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串，s中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅使用单个空格分隔，且不包含任何额外的空格。

解法一：调用API

Java语言为我们提供了现成的API，比如split拆分,reverse翻转，join连接等方法，因此我们可以简单的调用内置的API完成操作

解题思路：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

过程如下：

• 1、使用split将字符串按空格分割成字符串数组
• 2、使用reverse将字符串数组进行反转
• 3、使用join方法将字符串数组拼成一个字符串

    public String reverseWords(String s) {
        //除去多余的字符串
        s = s.trim();
        //正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ",wordList);
    }

解法二：原生函数编写

在解法一种，我们使用的是直接调用API的方法

其实我们也可以不使用语言中的API，而是自己编写对应的函数

在不同的语言中，这些函数的实现是不同的，主要的差别是有些语言的字符串不可变（如java和python），有些语言的字符串可变（如c++）

对于字符串不可变的语言，我们首先得把字符串转化为其他可变的数据结构，同时还需要在转化的过程中去除空格

解题思路：

想一下，我们将整个字符串都反转过来，那么单词的顺序也会变成倒序，只不过单词本身的各个字符也编程逆序了，那么我们再把单词反转一下，就可以实现

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

举个例子，源字符串为："the sky is blue "

• 移除多余空格 : “the sky is blue”
• 字符串反转：“eulb si yks eht”
• 单词反转：“blue is sky the”

    public String reverseWords(String s) {
        //1、去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        //2、反转整个字符串
        reverseString(sb,0,sb.length()-1);
        //3、反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    //去除字符串首尾以及中间多余空格
    public StringBuilder removeSpace(String s){
        int start = 0;
        int end = s.length()-1;
        while(s.charAt(start)==' '){
            start++;
        }
        while(s.charAt(end)==' '){
            end--;
        }
        StringBuilder sb = new StringBuilder();
        while(start<=end){
            char c = s.charAt(start);
            if(c!=' '||sb.charAt(sb.length()-1)!=' '){
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    //反转指定区间[start,end]内的字符
    public void reverseString(StringBuilder sb,int start,int end){
        while(start<end){
            char temp = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
    }

    //反转各个单词
    private void reverseEachWord(StringBuilder sb){
        int start = 0;
        int end = 1;
        int n = sb.length();
        while(start<n){
            while(end<n&&sb.charAt(end)!=' '){
                end++;
            }
        reverseString(sb,start,end-1);
        start = end+1;
        end = start+1;
        }
    }