Reverse

类型1: 只reverse单词顺序

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

可以用StringBuilder；也可以用reverse全部字母+reverse每个单词中的字母+remove空格

    public String reverseWords(String s) {
        String[] arr = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            String str = arr[i].trim();
            if (str.length() > 0) {
                sb.append(str).append(" ");
            }
        }
        return sb.toString().trim();
    }

类型2: 不改变单词顺序，改变每个单词中的字母顺序

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

可以用StringBuilder；也可以找到每个单词，然后单独颠倒字母顺序

    // 方法1
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String w : words) {
            sb.append(new StringBuilder(w).reverse().toString() + " ");
        }
        return sb.toString().trim();
    }
    
    // 方法2 + two pointers
    public String reverseWords(String s) {
        int lastEnd = -1;
        char[] arr = s.toCharArray();
        int len = s.length();
        
        for (int i = 0; i <= len; i++) {
            if (i == len || arr[i] == ' ') {
                int start = lastEnd + 1;
                int end = i - 1;
                
                while (start < end) {
                    char temp = arr[start];
                    arr[start] = arr[end];
                    arr[end] = temp;
                    start++;
                    end--;
                }
                lastEnd = i;
            }
        }
        return new String(arr);
    }
    
    // 方法2 + 用StringBuilder储存颠倒过后的单词
    public String reverseWords(String s) {
        StringBuilder result = new StringBuilder();
        int lastSpaceIndex = -1;
        for (int strIndex = 0; strIndex < s.length(); strIndex++) {
            if ((strIndex == s.length() - 1) || s.charAt(strIndex) == ' ') {
                int reverseStrIndex = (strIndex == s.length() - 1) ? strIndex : strIndex - 1;
                for (; reverseStrIndex > lastSpaceIndex; reverseStrIndex--) {
                    result.append(s.charAt(reverseStrIndex));
                }
                if (strIndex != s.length() - 1) {
                    result.append(' ');
                }
                lastSpaceIndex = strIndex;
            }
        }
        return new String(result);
    }