LeetCode 151 Reverse Words in a String

思路1

不用split和trim函数。使用一个stack来从前往后存储单词，最后再依次pop出来即可。

复杂度

时间复杂度O(n), 空间复杂度O(n)

代码

class Solution {
    public String reverseWords(String s) {
    if(s.length() == 0)return "";Stack<String> stack = new Stack<>();String tmp = "";for(int i = 0; i < s.length(); i++) {
    if(s.charAt(i) == ' ' && !tmp.equals("")) {
    stack.push(tmp);tmp = "";} else if(s.charAt(i) != ' ') {
    tmp += s.charAt(i);}}// push stack one more timeif(tmp.length() > 0)stack.push(tmp);String ans = "";while(!stack.isEmpty()) {
    ans = ans + stack.pop();System.out.println(ans);if(stack.size() > 0) {
    ans = ans + " ";}}return ans;}
}

【代码里使用的是直接将String拼接在一起，实际上很消耗时间，因为String是不可变对象。应该使用StringBuilder优化效率】

思路2

使用split将string分割成n个数组，然后从后向前组成字符串即可。

复杂度

时间复杂度O(n), 空间复杂度O(n)

代码

class Solution {
    public String reverseWords(String s) {
    if(s.length() == 0)return "";String[] sub = s.split(" ");StringBuilder sb = new StringBuilder();for(int i = sub.length-1; i >= 0; i--) {
    if(!sub[i].equals("")) {
    // 将空格视为单词前的组合，在单词前面加// 空格+单词的模式，考虑第一个单词的特殊情况if(sb.length() > 0)sb.append(" ");sb.append(sub[i]);}}return sb.toString();}
}

【注意split函数的使用，假设字符串为" k kk "，根据空格来split的话会分成4块，分别是第一个空格，第一个k，第二个空格，然后是kk，最后的空格没有计入】