問題描述

在處理字符串相關(guān)的問題時，反轉(zhuǎn)字符串中每個單詞的字符順序是一個常見的任務(wù)，同時要保證空格和單詞的初始順序不變。

給定一個字符串 s ，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。

• s 包含可打印的 ASCII 字符。
• s 不包含任何開頭或結(jié)尾空格。
• s 里 至少 有一個詞。
• s 中的所有單詞都用一個空格隔開。

下面我們將詳細(xì)介紹兩種解決該問題的方法，包括其解題思路和具體實(shí)現(xiàn)細(xì)節(jié)。

基于快慢指針的解法

1. 解題思路

快慢指針是一種常用的技巧，在本題中，快指針用于遍歷字符串，慢指針用于標(biāo)記每個單詞的起始位置。

當(dāng)快指針遇到空格時，就表示一個單詞已經(jīng)遍歷完，此時可以對慢指針到快指針之間的字符進(jìn)行反轉(zhuǎn)。

遍歷完整個字符串后，還需要對最后一個單詞進(jìn)行反轉(zhuǎn)，因?yàn)樽詈笠粋€單詞后面沒有空格來觸發(fā)反轉(zhuǎn)操作。同時，這也對只要一個單詞的情況進(jìn)行了處理

2. 代碼實(shí)現(xiàn)

class Solution {
public:
    string reverseWords(string s) //快慢指針解法
    {
        string::iterator fast = s.begin();
        string::iterator slow = s.begin();
 
        while( fast != s.end() )//快指針走完就結(jié)束
        {
            if(*fast==' ') //快指針走到空格位置停下，反轉(zhuǎn)該部分字母
            {
                reverse(slow,fast);
                slow = fast+1;
            }
            ++fast;
        }
        reverse(slow,fast);//出循環(huán)時，慢指針留在最后一個單詞的第一個字母
                           //快指針在\0位置，還需要反轉(zhuǎn)一次
        //同時可以對只要一個單詞的string處理
        return s;
 
    }
};

3. 代碼細(xì)節(jié)分析

• 指針初始化：首先定義了快指針 fast 和慢指針 slow，并將它們都初始化為字符串 s 的起始位置 s.begin()。
• 遍歷字符串：通過 while 循環(huán)，只要快指針 fast 沒有到達(dá)字符串末尾 s.end()，就繼續(xù)循環(huán)。
• 單詞反轉(zhuǎn)：當(dāng)快指針 fast 指向的字符為空格時，說明一個單詞已經(jīng)遍歷完，此時調(diào)用 reverse 函數(shù)將慢指針 slow 到快指針 fast 之間的字符進(jìn)行反轉(zhuǎn)。然后將慢指針 slow 移動到下一個單詞的起始位置，即 fast + 1。
• 最后一個單詞處理：循環(huán)結(jié)束后，慢指針 slow 停留在最后一個單詞的起始位置，快指針 fast 指向字符串末尾的下一個位置（即 \0 的位置），此時再調(diào)用一次 reverse 函數(shù)對最后一個單詞進(jìn)行反轉(zhuǎn)。
• 返回結(jié)果：最后返回反轉(zhuǎn)后的字符串 s。

基于索引的解法

1. 解題思路

這種方法使用索引來遍歷字符串，通過一個變量記錄每個單詞的起始位置，當(dāng)遇到空格或者字符串結(jié)束時，對當(dāng)前單詞進(jìn)行反轉(zhuǎn)。

2. 代碼實(shí)現(xiàn)

#include <iostream>
#include <string>
#include <algorithm>
 
class Solution {
public:
    string reverseWords(string s) {
        int start = 0; // 慢指針，標(biāo)記每個單詞的起始位置
        for (int end = 0; end <= s.length(); ++end) {
            // 當(dāng)遇到空格或者字符串結(jié)束時，反轉(zhuǎn)當(dāng)前單詞
            if (end == s.length() || s[end] == ' ') {
                // 反轉(zhuǎn)從 start 到 end - 1 的字符
                std::reverse(s.begin() + start, s.begin() + end);
                // 更新慢指針到下一個單詞的起始位置
                start = end + 1;
            }
        }
        return s;
    }
};

3. 代碼細(xì)節(jié)分析

• 起始位置初始化：定義變量 start 來記錄每個單詞的起始位置，初始化為 0。
• 遍歷字符串：通過 for 循環(huán)，使用變量 end 遍歷字符串 s，循環(huán)條件為 end <= s.length()，這樣可以確保在字符串結(jié)束時也能處理最后一個單詞。
• 單詞反轉(zhuǎn)：當(dāng) end 等于字符串的長度 s.length() 或者 s[end] 為空格時，說明一個單詞已經(jīng)遍歷完，此時調(diào)用 std::reverse 函數(shù)將從 s.begin() + start 到 s.begin() + end 的字符進(jìn)行反轉(zhuǎn)。
• 更新起始位置：反轉(zhuǎn)完當(dāng)前單詞后，將 start 更新為 end + 1，即下一個單詞的起始位置。
• 返回結(jié)果：循環(huán)結(jié)束后，返回反轉(zhuǎn)后的字符串 s。

兩種方法的比較

• 時間復(fù)雜度：兩種方法的時間復(fù)雜度都是 O(n)，其中 n 是字符串的長度，因?yàn)槎夹枰闅v字符串一次，并且每個字符最多被反轉(zhuǎn)一次。
• 空間復(fù)雜度：兩種方法的空間復(fù)雜度都是 O(1)，因?yàn)槎贾皇褂昧顺?shù)級的額外空間。
• 代碼可讀性：基于索引的方法代碼相對更加簡潔，使用索引來處理字符串更加直觀，而基于快慢指針的方法需要對指針的操作有較好的理解

通過以上兩種方法的詳細(xì)介紹，我們可以根據(jù)具體的需求和個人習(xí)慣選擇合適的方法來解決反轉(zhuǎn)字符串中單詞字符順序的問題。

到此這篇關(guān)于C++反轉(zhuǎn)字符串中單詞的字符順序的兩種方法的文章就介紹到這了,更多相關(guān)C++反轉(zhuǎn)單詞字符順序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論