?LeetCode刷題實(shí)戰(zhàn)186：翻轉(zhuǎn)字符串里的單詞 II

示例：
輸入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
輸出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

注意：
單詞的定義是不包含空格的一系列字符
輸入字符串中不會(huì)包含前置或尾隨的空格
單詞與單詞之間永遠(yuǎn)是以單個(gè)空格隔開(kāi)的

進(jìn)階：使用 O(1) 額外空間復(fù)雜度的原地解法。

class?Solution?{
public?void?reverseWords(char[] str)?{
????????int?i = 0;
????????for?(int?j = 0; j < str.length; j++) { // aTbTc
????????????if?(str[j] == ' ') {
????????????????reverse(str, i, j);
????????????????i = j + 1;
????????????}
????????}
????????reverse(str, i, str.length); // 最后一個(gè)單詞末尾沒(méi)有空格
????????System.out.println(String.valueOf(str));
????????reverse(str, 0, str.length); // 整體再翻轉(zhuǎn)一次
????}

????/**
?????* 將 str 的 [i, j] 進(jìn)行翻轉(zhuǎn)，如 "the" 轉(zhuǎn)換后變成 “eht”
?????* 注意，[i,j] 是左閉右開(kāi)
?????*
?????* @param?str
?????* @param?i
?????* @param?j
?????*/
????private?void?reverse(char[] str, int?i, int?j)?{
????????for?(int?k = i; k < (i + j) / 2; k++) {
????????????char?tmp = str[k]; // 位置 k 的元素
????????????int?g = j - 1?- k + i; // 位置 k 的對(duì)稱位置
????????????str[k] = str[g];
????????????str[g] = tmp;
????????}
????}
}