【LeetCode刷题日记】：151翻转字符串的单词（两种解法）

输入：s = "the sky is blue"
输出："blue is sky the"

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

 char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;

start → h e l l o   w o r l d ← end
        0 1 2 3 4 5 6 7 8 9 10 11

 private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

java

char temp = sb.charAt(start);        // 步骤1：暂存左边的字符
sb.setCharAt(start, sb.charAt(end)); // 步骤2：把右边字符放到左边位置
sb.setCharAt(end, temp);             // 步骤3：把暂存的左边字符放到右边位置

java

start++;  // 左指针右移
end--;    // 右指针左移

初始: o  l  l  e  h     w  o  r  l  d
      0  1  2  3  4  5  6  7  8  9  10
                      ↑
                   空格位置

java

reverseString(sb, 0, 4);  // 反转索引0~4
// "olleh" → "hello"

class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

//解法二：创建新字符数组填充。时间复杂度O(n)
class Solution {
    public String reverseWords(String s) {
        //源字符数组
        char[] initialArr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回
        int newArrPos = 0;
        //i来进行整体对源字符数组从后往前遍历
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
            //此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}

// 跳过空格
i=15: ' ' → i=14
i=14: ' ' → i=13
i=13: 'd' → 停止

right = i = 13

// 向左找单词左边界
i=13: 'd' ≠ ' ' → i=12
i=12: 'l' ≠ ' ' → i=11
i=11: 'r' ≠ ' ' → i=10
i=10: 'o' ≠ ' ' → i=9
i=9:  'w' ≠ ' ' → i=8
i=8:  ' ' == ' ' → 停止

// 单词范围 [i+1, right] = [9, 13]
// 复制 "world" + 空格
newArr: [w][o][r][l][d][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
        0  1  2  3  4  5
newArrPos = 6

// i 当前是 8，指向空格，继续跳过空格
i=8: ' ' → i=7
i=7: ' ' → i=6
i=6: 'o' → 停止

right = i = 6

// 向左找单词左边界
i=6: 'o' ≠ ' ' → i=5
i=5: 'l' ≠ ' ' → i=4
i=4: 'l' ≠ ' ' → i=3
i=3: 'e' ≠ ' ' → i=2
i=2: 'h' ≠ ' ' → i=1
i=1: ' ' == ' ' → 停止

// 单词范围 [i+1, right] = [2, 6]
// 复制 "hello" + 空格
newArr: [w][o][r][l][d][ ][h][e][l][l][o][ ][ ][ ][ ][ ][ ]
        0  1  2  3  4  5  6  7  8  9  10 11
newArrPos = 12