version at: 2022-4-7

/**
1. 单独反转每个word, 然后反转整个string
*/
class Solution {
    public String reverseWords(String s) {
        StringBuilder buffer = new StringBuilder();
        int n = s.length();

        for (int i = 0, j = 0; i < n && j < n && i <= j; i = j) {
            while (i < n && s.charAt(i) == ' ') i++;
            j = i;
            while (j < n && s.charAt(j) != ' ') j++;

            if (i < s.length() && j - 1 < s.length() && i <= j) record(s, i, j-1, buffer);
        }        

        buffer.setLength(buffer.length() - 1);
        return buffer.reverse().toString();
    }

    void record(String s, int i, int j, StringBuilder buffer) {
        while (i < s.length() && j < s.length() && i <= j) {
            if (s.charAt(j) != ' ') {
                buffer.append(s.charAt(j));
            }

            j--;
        }
        buffer.append(' ');
    }
}

/*
1. 翻转字符串中的所有单词， 双指针翻转整个数组，再翻转每个单词
2. 除去前导0，后缀0，遍历一次删除所有空格
3. testcase： null， “”， “    ”， “  abc 123  ”， “ abc 123”， “abc123 ”

4. 题目中要求C程序用 O（1） 的额外空间，其实主要是说去重复空格的时候用O（1） 的空间去除，其他语言也可实现
5. 整体的时间复杂度O（n）
*/


class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;
        int l = 0, r = s.length() - 1;
        char[] array = s.toCharArray();
        while (l <= r && s.charAt(l) == ' ') l++;
        if (l == r && s.charAt(l) == ' ') return "";
        while (l <= r && s.charAt(r) == ' ') r--;


        reverseSegment(array, l, r);
        int i = l, j = l;
        while (i <= r && j <= r){
            while (j <= r && array[j] != ' ') j++;
            reverseSegment(array, i, j-1);
            while (j <= r && array[j] == ' ') j++;
            i = j;
        }

        return String.valueOf(deleteMidSpace(array, l, r));

    }

    public char[] deleteMidSpace(char[] array, int l, int r){
        int i = l;
        int j = l;
        while (i <= r && j <= r){
            while (i <= r && array[i] != ' ') i ++;
            if (i < r && array[++i] == ' ') break;
        }
        if (i == r + 1) return Arrays.copyOfRange(array, l, i);

        j = i;
        while (i <= r && j <= r){
            while(j <= r && array[j] == ' ') j++;
            while(j <= r && array[j] != ' ') array[i++] = array[j++];
            array[i++] = ' ';
        }

        return Arrays.copyOfRange(array, l, i-1);
    }

    public void reverseSegment(char[] a, int l , int r){
        while (l < r){
            char t = a[l];
            a[l++] = a[r];
            a[r--] = t;
        }
    }
}