題目描述

牛客最近來了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志，寫些句子在本子上。同事Cat對(duì)Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來才意識(shí)到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”。Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么？

解法一：

遍歷一遍字符串發(fā)現(xiàn)是最后的單詞先輸出，和棧后進(jìn)先出的特性符合，因此可以用棧來解決。由于要保證輸出時(shí)單詞的順序是正的，就要將單詞作為一個(gè)整體String來存儲(chǔ)輸出。

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());
            }
            // 末尾符號(hào)需要特殊處理
            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();
    }
}

解法二：

另一種空間復(fù)雜度為O（n）的解法。利用String.split函數(shù)對(duì)字符串進(jìn)行切分，類似的還有jdk的Patter.split, apache的StringUtils.split、正則表達(dá)式、StringTokenizer以及indexOf+substring

關(guān)于各種方式的比較見另一片博文“多種字符串切分方法比較”

利用空格對(duì)字符串進(jìn)行切分。

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(" ");
        }
        //去掉最后最后多加的一個(gè)空格，并且保證在str只為一個(gè)空格時(shí)不會(huì)被去掉
        if(sb.length() >= 1)
            sb.delete(sb.length() - 1, sb.length());
        return sb.toString();
    }
}

解法三：

第一步：翻轉(zhuǎn)所有字符
第二步：翻轉(zhuǎn)單詞
翻轉(zhuǎn)可以由自定義一個(gè)翻轉(zhuǎn)函數(shù)來完成。
由于String不可變，可以將String轉(zhuǎn)換為數(shù)組進(jìn)行操作。

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++;
        }
                //重要，對(duì)最后一個(gè)單詞進(jìn)行翻轉(zhuǎn)，同時(shí)防止str只為一個(gè)單詞不包含空格時(shí)造成的只翻轉(zhuǎn)了一次
        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--;
        }
    }
}

我們是因?yàn)镾tring不可變而采用的數(shù)組，同樣的道理也可以使用StringBuilder，因?yàn)镾tringBuilder可變

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--;
        }
    }
}

這幾種方法的時(shí)間復(fù)雜度均為O（n），空間復(fù)雜度也均為O（n）