func reverseWords(s string) string {
    words := strings.Fields(s)
    slices.Reverse(words)
    return strings.Join(words, " ")
}

class Solution {
public:
    string reverseWords(string s) {
        removeExtraSpaces(s);
        
        reverse(s.begin(), s.end());

        string::iterator gh = s.begin();
        for (auto p = s.begin(); p != s.end(); p++) {
            if (*p == ' ') {
                reverse(gh, p);
                gh = p+1;
                continue;
            }
        }
        reverse(gh, s.end());

        return s;
    }

    void removeExtraSpaces(string& s) {
        int slow = 0;
        int fast = 0;
        
        while (fast < s.size() && s[fast] == ' ') {
            fast++;
        }
        
        bool isSpace = false;  // 标记前一个字符是否为空格
        while (fast < s.size()) {
            if (s[fast] == ' ') {
                if (!isSpace) {  // 当前是空格，且前一个不是空格
                    s[slow++] = ' ';
                    isSpace = true;
                }
            } else {  // 非空格字符
                s[slow++] = s[fast];
                isSpace = false;
            }
            fast++;
        }
        
        if (slow > 0 && s[slow - 1] == ' ') {
            slow--;
        }
        
        s.resize(slow);
    }

    
};

func rotate(matrix [][]int)  {
    n := len(matrix)
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }

    for i := 0; i < n; i++ {
        slices.Reverse(matrix[i])
    }
}

func rotate(matrix [][]int)  {
    n := len(matrix)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ {
            matrix[i][j], matrix[n-j-1][n-i-1] = matrix[n-j-1][n-i-1], matrix[i][j]
        }
    }

    for i := 0; i < n; i++ {
        slices.Reverse(matrix[i])
    }
}

func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0]) // matrix: m rows * n cols
    total := m * n
 
    T := 0
    B := m-1
    L := 0
    R := n-1

    result := make([]int, 0, total)

    for len(result) < total {
        // top
        if T <= B {
            i := T
            for j := L; j <= R; j++ {
                result = append(result, matrix[i][j])
            }
            T++
        }

        // right
        if L <= R {
            j := R
            for i := T; i <= B; i++ {
                result = append(result, matrix[i][j])
            }
            R--
        }
        
        // bottom
        if T <= B {
            i := B
            for j := R; j >= L; j-- {
                result = append(result, matrix[i][j])
            }
            B--
        }
        
        // left
        if L <= R {
            j := L
            for i := B; i >= T; i-- {
                result = append(result, matrix[i][j])
            }
            L++
        }
    }

    return result
}

func generateMatrix(n int) [][]int {
    T := 0
    B := n-1
    L := 0
    R := n-1

    matrix := createMatrix(n)

    x := 1
    total := n*n

    for x <= total {
        // top
        if T <= B {
            i := T
            for j := L; j <= R; j++ {
                matrix[i][j] = x
                x++
            }
            T++
        }

        // right
        if L <= R {
            j := R
            for i := T; i <= B; i++ {
                matrix[i][j] = x
                x++
            }
            R--
        }

        // bottom
        if T <= B {
            i := B
            for j := R; j >= L; j-- {
                matrix[i][j] = x
                x++
            }
            B--
        }

        // left
        if L <= R {
            j := L
            for i := B; i >= T; i-- {
                matrix[i][j] = x
                x++
            }
            L++
        }
    }

    return matrix
}

func createMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    return matrix
}

func isPalindrome(s string) bool {
    i, j := -1, len(s)

    for {
        i++
        j--

        for i < j && !isValid(s[i]) { i++ }
        for i < j && !isValid(s[j]) { j-- }

        if i >= j {
            break
        }

        if !equal(s[i], s[j]) {
            return false
        }
    }

    return true
}

func isValid(c byte) bool {
    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

func equal(a, b byte) bool {
    return a == b || lower(a) == lower(b)
}

func lower(b byte) byte {
    if b >= 'A' && b <= 'Z' {
        return b - 'A' + 'a'
    }

    return b
}