151.翻轉字符串里的單詞

建議：這道題目基本把 剛剛做過的字符串操作 都覆蓋了，不過就算知道解題思路，本題代碼并不容易寫，要多練一練。

題目鏈接/文章講解/視頻講解：代碼隨想錄

我們這道題的思路是，先將整個字符串反轉，結束之后再定位每一個單詞，然后再將單詞進行反轉，思路為什么是這樣子的呢

為什么要先翻轉整個字符集，再翻轉單詞，而不是直接翻轉單詞

假設輸入字符串: "hello world"

方法1 (當前代碼采用的方法):
1. 整體翻轉: "dlrow olleh"
2. 單詞翻轉: "world hello"

方法2 (直接翻轉單詞):
這需要:
1. 找到每個單詞的位置
2. 將單詞存儲到新的位置
3. 處理單詞之間的空格
4. 可能需要額外的存儲空間來臨時保存單詞

當前方法的優勢:
1. 空間復雜度低：只需要在原字符串上操作，不需要額外空間存儲單詞
2. 實現簡單：只需要簡單的字符交換操作
3. 時間復雜度穩定：只需要遍歷字符串固定的次數

直接翻轉單詞的劣勢:
1. 需要額外的空間來存儲單詞
2. 需要處理單詞移動的復雜邏輯
3. 實現起來更復雜，容易出錯
?

如果我們直接對單詞進行反轉，我舉個例子

“hello world”

反轉之后應該是“world hello”

如果不將字符串先進行反轉，我們直接反轉的話，需要額外的空間，因為數組的操作從根本上來說是覆蓋操作，那么我們在寫world的時候就會將hello覆蓋，所以我們需要格外的空間存儲hello才行，這樣就把邏輯變復雜了，如果先翻轉再單詞內部反轉，適度簡化了邏輯。

我們來看代碼

public String reverseWords(String s) {// 第一步：調用removeSpace去除多余空格StringBuilder sb = removeSpace(s);// 第二步：反轉整個字符串reverseString(sb, 0, sb.length() - 1);// 第三步：反轉每個單詞reverseEachWord(sb);// 返回最終結果return sb.toString();
}
private StringBuilder removeSpace(String s) {// 定義雙指針，用于確定字符串的有效范圍（去除首尾空格）int start = 0;int end = s.length() - 1;// 移動start指針，跳過開頭的空格while (s.charAt(start) == ' ') start++;// 移動end指針，跳過結尾的空格while (s.charAt(end) == ' ') end--;// 創建StringBuilder存儲結果StringBuilder sb = new StringBuilder();// 處理中間的空格，確保單詞之間只有一個空格while (start <= end) {char c = s.charAt(start);// 當前字符不是空格，或者當前字符是空格但前一個字符不是空格時，才添加if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}start++;}return sb;
}
public void reverseString(StringBuilder sb, int start, int end) {// 使用雙指針從兩端向中間移動while (start < end) {// 交換start和end位置的字符char temp = sb.charAt(start);sb.setCharAt(start, sb.charAt(end));sb.setCharAt(end, temp);// 移動指針start++;end--;}
}
private void reverseEachWord(StringBuilder sb) {// start指向單詞的開始，end指向下一個字符int start = 0;int end = 1;int n = sb.length();while (start < n) {// 移動end直到找到單詞的結束位置（空格或字符串末尾）while (end < n && sb.charAt(end) != ' ') {end++;}// 反轉當前單詞reverseString(sb, start, end - 1);// 更新start和end，準備處理下一個單詞start = end + 1;end = start + 1;}
}

卡碼網：55.右旋轉字符串

建議：題解中的解法如果沒接觸過的話，應該會想不到

題目鏈接/文章講解：

右旋轉