剑指offer-44-反转单词顺序

思路

• 栈+指针
  利用栈来反转句子，利用一个指针指向空格，for循环中的i算是尾指针，指向下一个空格。对每个单词和空格入栈。
  时间复杂度O(n)
• split分割成字符串
  然后从后往前拼接

代码

栈+指针

public class Solution {
    public String ReverseSentence(String str){
        Stack stack = new Stack();
        int l = 0;
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == " "){
                System.out.println(l+" "+i);
                stack.push(str.substring(l, i));
                l = i;
                stack.push(" ");
                l++;
            }
            if(i == str.length() - 1){
                stack.push(str.substring(l));
            }
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.toString();
    }
}

split函数分割字符串

public class Solution {
    public String ReverseSentence(String str) {
        String[] s= str.split(" ");
        if(s.length<=1){return str;}
        String res="";
        for(int i=s.length-1; i>0;i--){
            res+=s[i]+" ";
        }
        res+=s[0];
        return res;
    }
}