翻转单词顺序序列

题目描述

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

解法一：

遍历一遍字符串发现是最后的单词先输出，和栈后进先出的特性符合，因此可以用栈来解决。由于要保证输出时单词的顺序是正的，就要将单词作为一个整体String来存储输出。

public class Solution {
    public static String ReverseSentence(String str) {
        Stack<String> stack = new Stack<String>();
        StringBuilder word = new StringBuilder();
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ') {
                stack.push(word.toString());
                stack.push(String.valueOf(str.charAt(i)));
                word.delete(0, word.length());
            }
            // 末尾符号需要特殊处理
            else if(i == str.length() - 1)
                stack.push(word.toString() + String.valueOf(str.charAt(i)));
            else
                word.append(str.charAt(i));
        }
        while(!stack.isEmpty())
            result.append(stack.pop());
        return result.toString();
    }
}

解法二：

另一种空间复杂度为O（n）的解法。利用String.split函数对字符串进行切分，类似的还有jdk的Patter.split, apache的StringUtils.split、正则表达式、StringTokenizer以及indexOf+substring

关于各种方式的比较见另一片博文“多种字符串切分方法比较”

利用空格对字符串进行切分。

public class Solution {
    public static String ReverseSentence(String str) {
        String [] data = str.split(" ");
        StringBuilder sb = new StringBuilder();
        if(data.length == 0)
            return str;
        for(int i = data.length - 1; i >= 0; i--) {
            sb.append(data[i]);
            sb.append(" ");
        }
        //去掉最后最后多加的一个空格，并且保证在str只为一个空格时不会被去掉
        if(sb.length() >= 1)
            sb.delete(sb.length() - 1, sb.length());
        return sb.toString();
    }
}

解法三：

第一步：翻转所有字符
第二步：翻转单词
翻转可以由自定义一个翻转函数来完成。
由于String不可变，可以将String转换为数组进行操作。

public class Solution {
    public static String ReverseSentence(String str) {
        char [] reverse = str.toCharArray();
        Reverse(reverse, 0, reverse.length - 1);
        int start = 0, end = 0;
        while(end < reverse.length) {
            if(reverse[end] == ' ') {
                Reverse(reverse, start, --end);
                end += 2;
                start = end;
            }
            else 
                end++;
        }
                //重要，对最后一个单词进行翻转，同时防止str只为一个单词不包含空格时造成的只翻转了一次
        Reverse(reverse, start, end - 1);
        return new String(reverse);
    }
    public static void Reverse(char [] str, int start, int end) {
        char tmp;
        while(start < end) {
            tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            start++;
            end--;
        }
    }
}

我们是因为String不可变而采用的数组，同样的道理也可以使用StringBuilder，因为StringBuilder可变

public class Solution {
    public static String ReverseSentence(String str) {
        StringBuilder sb = new StringBuilder(str);
        Reverse(sb, 0, sb.length() - 1);
        int start = 0, end = 0;
        while(end < sb.length()) {
            if(sb.charAt(end) == ' ') {
                Reverse(sb, start, --end);
                end += 2;
                start = end;
            }
            else 
                end++;
        }
        Reverse(sb, start, end - 1);
        return sb.toString();
    }
    public static void Reverse(StringBuilder sb, int start, int end) {
        char tmp;
        while(start < end) {
            tmp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, tmp);
            start++;
            end--;
        }
    }
}

这几种方法的时间复杂度均为O（n），空间复杂度也均为O（n）