剑指 Offer 58 - I. 翻转单词顺序

剑指 Offer 58 - I. 翻转单词顺序

解法一

不用内置方法

1. 去除首尾空格和中间多余空格
2. 翻转所有字符
3. 翻转每个单词

class Solution {
    public String reverseWords(String s) {
        // 去除首尾空格和中间多余空格
        char[] ch = trim(s);
        // 翻转所有字符
        reverse(ch, 0, ch.length - 1);
        // 翻转每个单词
        reverseWord(ch);
        return new String(ch);
    }

    char[] trim(String s){
        StringBuilder sb = new StringBuilder();
        int l = 0, r = s.length() - 1;
        while(l <= r && s.charAt(l) == ' ') l++;
        while(l <= r && s.charAt(r) == ' ') r--;
        for(int i = l; i <= r; i++){
            if(s.charAt(i) != ' ') sb.append(s.charAt(i));
            else {
                if(s.charAt(i + 1) != ' ') sb.append(' ');  // 只加入连续空格的最后一个
            }
        } 
        return sb.toString().toCharArray(); 
    }

    void reverseWord(char[] ch){
        int l = 0, r = 0;
        while(r < ch.length){
            while(r < ch.length && ch[r] != ' ') r++;
            reverse(ch, l, r - 1);
            l = r + 1;
            r = r + 1;
        }
    }

    void reverse(char[] ch, int l, int r){
        while(l < r){
            char tmp = ch[l];
            ch[l] = ch[r];
            ch[r] = tmp;
            l++;
            r--;
        }
    }
}

解法二

用自带的 trim() 和 substring()，要自己实现这两个方法也很简单。

class Solution {
    public String reverseWords(String s) {
        s = s.trim();  // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0){
            while(i >= 0 && s.charAt(i) != ' ') i--;  // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " ");  // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--;  // 跳过单词间空格
            j = i;  // j 指向下个单词的尾字符
        }
        return res.toString().trim();  // 转化为字符串并返回
    }
}