🌗 151. 颠倒字符串中的单词

难度: 🌗

问题描述

---

解法

class Solution {
    public String reverseWords(String s) {
        // 思路：
        // String 属于 不可变类型，要想转换成可变，需要变为 StringBuilder 之类
        // 但转换为 sb 之后，要原地删除空格就复杂了，要把空格后所有元素全部前移，如果空格多，需要多次全移
        // 复杂度肯定上升，所以只能使用 append() 实现，这样虽然不是原地，但是复杂度不会升高
        // 从右往左依次找到单词
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        int cur = len - 1;
        while(cur >= 0) {
            while(cur >= 0 && s.charAt(cur) == ' ') {
                cur --;
            }
            if(cur < 0) {
                sb.deleteCharAt(sb.length() - 1);
                return sb.toString();
            }
            // cur >= 0
            int prev = cur;
            while(prev >= 0 && s.charAt(prev) != ' ') {
                prev --;
            }
            // [prev + 1, cur]
            sb.append(s.substring(prev + 1, cur + 1)).append(" ");
            cur = prev;
        }
        sb.deleteCharAt(sb.length() - 1); // 题意给出 s 至少存在一个单词，不用特殊情况特判
        return sb.toString();
    }
}

---

输出