???????????💓 博客主頁：倔強的石頭的CSDN主頁?
???????????📝Gitee主頁：倔強的石頭的gitee主頁
? ? ? ? ? ? ? 文章專欄：C++經典例題
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????期待您的關注
?
目錄
問題描述
基于快慢指針的解法
基于索引的解法
兩種方法的比較
?
問題描述
在處理字符串相關的問題時，反轉字符串中每個單詞的字符順序是一個常見的任務，同時要保證空格和單詞的初始順序不變。
?
給定一個字符串?s?，你需要反轉字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。
s?包含可打印的?ASCII?字符。s?不包含任何開頭或結尾空格。s?里?至少?有一個詞。s?中的所有單詞都用一個空格隔開。
原題鏈接：557. 反轉字符串中的單詞 III - 力扣（LeetCode）
下面我們將詳細介紹兩種解決該問題的方法，包括其解題思路和具體實現細節。
?
基于快慢指針的解法
1. 解題思路
快慢指針是一種常用的技巧，在本題中，快指針用于遍歷字符串，慢指針用于標記每個單詞的起始位置。當快指針遇到空格時，就表示一個單詞已經遍歷完，此時可以對慢指針到快指針之間的字符進行反轉。
遍歷完整個字符串后，還需要對最后一個單詞進行反轉，因為最后一個單詞后面沒有空格來觸發反轉操作。同時，這也對只要一個單詞的情況進行了處理
?
2. 代碼實現
class Solution {
public:string reverseWords(string s) //快慢指針解法{string::iterator fast = s.begin();string::iterator slow = s.begin();while( fast != s.end() )//快指針走完就結束{if(*fast==' ') //快指針走到空格位置停下，反轉該部分字母{reverse(slow,fast);slow = fast+1;}++fast;}reverse(slow,fast);//出循環時，慢指針留在最后一個單詞的第一個字母//快指針在\0位置，還需要反轉一次//同時可以對只要一個單詞的string處理return s;}
};
3. 代碼細節分析
- 指針初始化：首先定義了快指針 fast 和慢指針 slow，并將它們都初始化為字符串 s 的起始位置 s.begin()。
- 遍歷字符串：通過 while 循環，只要快指針 fast 沒有到達字符串末尾 s.end()，就繼續循環。
- 單詞反轉：當快指針 fast 指向的字符為空格時，說明一個單詞已經遍歷完，此時調用 reverse 函數將慢指針 slow 到快指針 fast 之間的字符進行反轉。然后將慢指針 slow 移動到下一個單詞的起始位置，即 fast + 1。
- 最后一個單詞處理：循環結束后，慢指針 slow 停留在最后一個單詞的起始位置，快指針 fast 指向字符串末尾的下一個位置（即 \0 的位置），此時再調用一次 reverse 函數對最后一個單詞進行反轉。
- 返回結果：最后返回反轉后的字符串 s。
?
基于索引的解法
1. 解題思路
這種方法使用索引來遍歷字符串，通過一個變量記錄每個單詞的起始位置，當遇到空格或者字符串結束時，對當前單詞進行反轉。
2. 代碼實現
#include <iostream>
#include <string>
#include <algorithm>class Solution {
public:string reverseWords(string s) {int start = 0; // 慢指針，標記每個單詞的起始位置for (int end = 0; end <= s.length(); ++end) {// 當遇到空格或者字符串結束時，反轉當前單詞if (end == s.length() || s[end] == ' ') {// 反轉從 start 到 end - 1 的字符std::reverse(s.begin() + start, s.begin() + end);// 更新慢指針到下一個單詞的起始位置start = end + 1;}}return s;}
};
3. 代碼細節分析
- 起始位置初始化：定義變量 start 來記錄每個單詞的起始位置，初始化為 0。
- 遍歷字符串：通過 for 循環，使用變量 end 遍歷字符串 s，循環條件為 end <= s.length()，這樣可以確保在字符串結束時也能處理最后一個單詞。
- 單詞反轉：當 end 等于字符串的長度 s.length() 或者 s[end] 為空格時，說明一個單詞已經遍歷完，此時調用 std::reverse 函數將從 s.begin() + start 到 s.begin() + end 的字符進行反轉。
- 更新起始位置：反轉完當前單詞后，將 start 更新為 end + 1，即下一個單詞的起始位置。
- 返回結果：循環結束后，返回反轉后的字符串 s。
?
兩種方法的比較
?
- 時間復雜度：兩種方法的時間復雜度都是?O(n)，其中?n?是字符串的長度，因為都需要遍歷字符串一次，并且每個字符最多被反轉一次。
- 空間復雜度：兩種方法的空間復雜度都是?O(1)，因為都只使用了常數級的額外空間。
- 代碼可讀性：基于索引的方法代碼相對更加簡潔，使用索引來處理字符串更加直觀，而基于快慢指針的方法需要對指針的操作有較好的理解
通過以上兩種方法的詳細介紹，我們可以根據具體的需求和個人習慣選擇合適的方法來解決反轉字符串中單詞字符順序的問題。
?
?
?
?
?
