剑指offer44

反转单词序列

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

输入

“nowcoder. a am I”

输出

“I am a nowcoder.”

解法一：使用 str.split拆分，然后 append 到 StringBuilder

public class Solution {
    public String ReverseSentence(String str) {

        //1 使用 str.split拆分，然后 append 到 StringBuilder
        if(str.trim().length()==0 || str==null)return str;
        StringBuilder sb = new StringBuilder();
        String[] strings = str.split(" ");
        int len = strings.length;
        for(int i=len-1;i>=0;i--){
            sb.append(strings[i]);
            sb.append(" ");
        }
        return sb.deleteCharAt(sb.length()-1).toString();   //删除末尾的空格
}

解法二：使用栈，出现倒序，自然地联想到栈“后进先出”的特点

import java.util.Stack;
public class Solution {
    public String ReverseSentence(String str) {

        //2 使用栈，出现倒序，自然地联想到栈“后进先出”的特点
        if (str.trim().equals("") && str.length() > 0)return str; 
        Stack<String> reverse = new Stack<>();
        String res = str.trim();
        String[] strings = res.split(" ");
        for (int i = 0; i<strings.length; i++) {
            reverse.push(strings[i]);
        }
        res = reverse.pop();
        while (!reverse.isEmpty()) {
            res = res + " " + reverse.pop();
        }
        return res;
        }
}

解法三：两次反转：先反转句子整体，再反转句子中每个子字符串

public class Solution {
    public String ReverseSentence(String str) {

        //3 两次反转：先反转句子整体，再反转句子中每个子字符串
        if(str.trim().length()==0 || str==null)return str;
        char[] chars = str.toCharArray();
        //整个句子反转
        reverse(chars, 0, chars.length-1);
        //分别反转里面的子字符串
        int start = 0, end = 0;
        while (end < chars.length){
            //碰到空格了，将里面的子字符串反转
            if (chars[end] == ' '){
                reverse(chars, start, end-1);
                start = end+1;    //下次跳过空格
            }
            //到最后一个，反转最后一个子字符串
            else if (end == chars.length-1){
                reverse(chars, start, end);
            }else {
            }
            end++;
        }

        return String.valueOf(chars);
    }
    /**
     * 反转方法
     * @param target
     * @param start
     * @param end
     */
    private static void reverse(char[] target, int start, int end){
        while (start < end){
            char tmp = target[start];
            target[start] = target[end];
            target[end] = tmp;
            start++;
            end--;
        }
    }
}