綜合考察字符串操作的好題。

151.翻轉(zhuǎn)字符串里的單詞

力扣題目鏈接

給定一個字符串，逐個翻轉(zhuǎn)字符串中的每個單詞。

示例 1：
輸入: “the sky is blue”
輸出: “blue is sky the”

示例 2：
輸入: " hello world! "
輸出: “world! hello”
解釋: 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。

示例 3：
輸入: “a good example”
輸出: “example good a”
解釋: 如果兩個單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個。

思路

這道題目可以說是綜合考察了字符串的多種操作。

一些同學(xué)會使用split庫函數(shù)，分隔單詞，然后定義一個新的string字符串，最后再把單詞倒序相加，那么這道題題目就是一道水題了，失去了它的意義。

所以這里我還是提高一下本題的難度：不要使用輔助空間，空間復(fù)雜度要求為O(1)。

不能使用輔助空間之后，那么只能在原字符串上下功夫了。

想一下，我們將整個字符串都反轉(zhuǎn)過來，那么單詞的順序指定是倒序了，只不過單詞本身也倒序了，那么再把單詞反轉(zhuǎn)一下，單詞不就正過來了。

所以解題思路如下：

• 移除多余空格
• 將整個字符串反轉(zhuǎn)
• 將每個單詞反轉(zhuǎn)

舉個例子，源字符串為："the sky is blue "

• 移除多余空格 : “the sky is blue”
• 字符串反轉(zhuǎn)：“eulb si yks eht”
• 單詞反轉(zhuǎn)：“blue is sky the”

這樣我們就完成了翻轉(zhuǎn)字符串里的單詞。

思路很明確了，我們說一說代碼的實(shí)現(xiàn)細(xì)節(jié)，就拿移除多余空格來說，一些同學(xué)會上來寫如下代碼：

void removeExtraSpaces(string& s) {
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // 刪除字符串最后面的空格
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // 刪除字符串最前面的空格
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}

邏輯很簡單，從前向后遍歷，遇到空格了就erase。

如果不仔細(xì)琢磨一下erase的時間復(fù)雜度，還以為以上的代碼是O(n)的時間復(fù)雜度呢。

想一下真正的時間復(fù)雜度是多少，一個erase本來就是O(n)的操作。

erase操作上面還套了一個for循環(huán)，那么以上代碼移除冗余空格的代碼時間復(fù)雜度為O(n^2)。

那么使用雙指針法來去移除空格，最后resize（重新設(shè)置）一下字符串的大小，就可以做到O(n)的時間復(fù)雜度。

//版本一 
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定義快指針，慢指針
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中間部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新設(shè)置字符串大小
    }
}

有的同學(xué)可能發(fā)現(xiàn)用erase來移除空格，在leetcode上性能也還行。主要是以下幾點(diǎn)；：

1. leetcode上的測試集里，字符串的長度不夠長，如果足夠長，性能差距會非常明顯。
2. leetcode的測程序耗時不是很準(zhǔn)確的。

版本一的代碼是一般的思考過程，就是 先移除字符串前的空格，再移除中間的，再移除后面部分。

不過其實(shí)還可以優(yōu)化，這部分和27.移除元素的邏輯是一樣一樣的，本題是移除空格，而 27.移除元素 就是移除元素。

所以代碼可以寫的很精簡，大家可以看 如下 代碼 removeExtraSpaces 函數(shù)的實(shí)現(xiàn)：

// 版本二 
void removeExtraSpaces(string& s) {//去除所有空格并在相鄰單詞之間添加空格, 快慢指針。
    int slow = 0;   //整體思想?yún)⒖糷ttps://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。
            if (slow != 0) s[slow++] = ' '; //手動控制空格，給單詞之間添加空格。slow != 0說明不是第一個單詞，需要在單詞前添加空格。
            while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說明單詞結(jié)束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即為去除多余空格后的大小。
}

如果以上代碼看不懂，建議先把 27.移除元素這道題目做了，或者看視頻講解：數(shù)組中移除元素并不容易！LeetCode：27. 移除元素 。

此時我們已經(jīng)實(shí)現(xiàn)了removeExtraSpaces函數(shù)來移除冗余空格。

還要實(shí)現(xiàn)反轉(zhuǎn)字符串的功能，支持反轉(zhuǎn)字符串子區(qū)間，這個實(shí)現(xiàn)我們分別在344.反轉(zhuǎn)字符串和541.反轉(zhuǎn)字符串II里已經(jīng)講過了。

代碼如下：

// 反轉(zhuǎn)字符串s中左閉右閉的區(qū)間[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}

整體代碼如下：

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻轉(zhuǎn)，區(qū)間寫法：左閉右閉 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相鄰單詞之間添加空格, 快慢指針。
        int slow = 0;   //整體思想?yún)⒖糷ttps://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。
                if (slow != 0) s[slow++] = ' '; //手動控制空格，給單詞之間添加空格。slow != 0說明不是第一個單詞，需要在單詞前添加空格。
                while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說明單詞結(jié)束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即為去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保證單詞之間之只有一個空格，且字符串首尾沒空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保證第一個單詞的開始下標(biāo)一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到達(dá)空格或者串尾，說明一個單詞結(jié)束。進(jìn)行翻轉(zhuǎn)。
                reverse(s, start, i - 1); //翻轉(zhuǎn)，注意是左閉右閉 []的翻轉(zhuǎn)。
                start = i + 1; //更新下一個單詞的開始下標(biāo)start
            }
        }
        return s;
    }
};

其他語言版本

Java：

class Solution {
   /**
     * 不使用Java內(nèi)置方法實(shí)現(xiàn)
     * <p>
     * 1.去除首尾以及中間多余空格
     * 2.反轉(zhuǎn)整個字符串
     * 3.反轉(zhuǎn)各個單詞
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中間多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反轉(zhuǎn)整個字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反轉(zhuǎn)各個單詞
        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;
    }

    /**
     * 反轉(zhuǎn)字符串指定區(qū)間[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;
        }
    }
}

//解法二：創(chuàng)建新字符數(shù)組填充。時間復(fù)雜度O(n)
class Solution {
    public String reverseWords(String s) {
        //源字符數(shù)組
        char[] initialArr = s.toCharArray();
        //新字符數(shù)組
        char[] newArr = new char[initialArr.length+1];//下面循環(huán)添加"單詞 "，最終末尾的空格不會返回
        int newArrPos = 0;
        //i來進(jìn)行整體對源字符數(shù)組從后往前遍歷
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //跳過空格
            //此時i位置是邊界或!=空格，先記錄當(dāng)前索引，之后的while用來確定單詞的首字母的位置
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //指定區(qū)間單詞取出(由于i為首字母的前一位，所以這里+1,)，取出的每組末尾都帶有一個空格
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串沒有單詞，直接返回空字符串；若是有單詞，返回0-末尾空格索引前范圍的字符數(shù)組(轉(zhuǎn)成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}

//解法三：雙反轉(zhuǎn)+移位，在原始數(shù)組上進(jìn)行反轉(zhuǎn)。空間復(fù)雜度O(1)
class Solution {
    /**
     * 思路：
     *	①反轉(zhuǎn)字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍歷 " eulb si yks eht"，每次先對某個單詞進(jìn)行反轉(zhuǎn)再移位
     *	   這里以第一個單詞進(jìn)行為演示：" eulb si yks eht" ==反轉(zhuǎn)=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //步驟1：字符串整體反轉(zhuǎn)（此時其中的單詞也都反轉(zhuǎn)了）
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //步驟二：二次反轉(zhuǎn)
                    reverse(initialArr, tempCur, i - 1);//對指定范圍字符串進(jìn)行反轉(zhuǎn)，不反轉(zhuǎn)從后往前遍歷一個個填充有問題
                }
                //步驟三：移動操作
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //遍歷結(jié)束
                    //避免越界情況，例如=> "asdasd df f"，不加判斷最后就會數(shù)組越界
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //參數(shù)三：以防出現(xiàn)如"asdasd df f"=>"f df asdasd"正好湊滿不需要省略空格情況
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    public void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            chars[i] ^= chars[j];
            chars[j] ^= chars[i];
            chars[i] ^= chars[j];
        }
    }
}

/*
 * 解法四：時間復(fù)雜度 O(n)
 * 參考卡哥 c++ 代碼的三步驟：先移除多余空格，再將整個字符串反轉(zhuǎn)，最后把單詞逐個反轉(zhuǎn)
 * 有別于解法一 ：沒有用 StringBuilder  實(shí)現(xiàn)，而是對 String 的 char[] 數(shù)組操作來實(shí)現(xiàn)以上三個步驟
 */
class Solution {
    //用 char[] 來實(shí)現(xiàn) String 的 removeExtraSpaces，reverse 操作
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1.去除首尾以及中間多余空格
        chars = removeExtraSpaces(chars);
        //2.整個字符串反轉(zhuǎn)
        reverse(chars, 0, chars.length - 1);
        //3.單詞反轉(zhuǎn)
        reverseEachWord(chars);
        return new String(chars);
    }

    //1.用 快慢指針 去除首尾以及中間多余空格，可參考數(shù)組元素移除的題解
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一個單詞外，單詞末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍歷到字符串末尾，就證明遍歷完一個單詞了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相當(dāng)于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //雙指針實(shí)現(xiàn)指定范圍內(nèi)字符串反轉(zhuǎn)，可參考字符串反轉(zhuǎn)題解
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3.單詞反轉(zhuǎn)
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 這里的 = ，是為了讓 end 永遠(yuǎn)指向單詞末尾后一個位置，這樣 reverse 的實(shí)參更好設(shè)置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到單詞末尾后的空格或串尾,開始反轉(zhuǎn)單詞
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}

python:

class Solution:
  #1.去除多余的空格
        def trim_spaces(self, s):     
            n = len(s)
            left = 0
            right = n-1
        
            while left <= right and s[left] == ' ':    #去除開頭的空格
                left += 1
            while left <= right and s[right] == ' ':   #去除結(jié)尾的空格
                right -= 1
            tmp = []
            while left <= right:                      #去除單詞中間多余的空格
                if s[left] != ' ':
                    tmp.append(s[left])
                elif tmp[-1] != ' ':                 #當(dāng)前位置是空格，但是相鄰的上一個位置不是空格，則該空格是合理的
                    tmp.append(s[left])
                left += 1
            return tmp
	    
 #2.翻轉(zhuǎn)字符數(shù)組
        def reverse_string(self, nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            return None
	    
 #3.翻轉(zhuǎn)每個單詞
        def reverse_each_word(self, nums):
            start = 0
            end = 0
            n = len(nums)
            while start < n:
                while end < n and nums[end] != ' ':
                    end += 1
                self.reverse_string(nums, start, end-1)
                start = end + 1
                end += 1
            return None

#4.翻轉(zhuǎn)字符串里的單詞
        def reverseWords(self, s):                #測試用例："the sky is blue"
            l = self.trim_spaces(s)               #輸出：['t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e'
            self.reverse_string(l,  0, len(l)-1)  #輸出：['e', 'u', 'l', 'b', ' ', 's', 'i', ' ', 'y', 'k', 's', ' ', 'e', 'h', 't']
            self.reverse_each_word(l)             #輸出：['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']
            return ''.join(l)                    #輸出：blue is sky the

class Solution:
    def reverseWords(self, s: str) -> str:
        # method 1 - Rude but work & efficient method.
        s_list = [i for i in s.split(" ") if len(i) > 0]
        return " ".join(s_list[::-1])

        # method 2 - Carlo's idea
        def trim_head_tail_space(ss: str):
            p = 0
            while p < len(ss) and ss[p] == " ":
                p += 1
            return ss[p:]

        # Trim the head and tail space
        s = trim_head_tail_space(s)
        s = trim_head_tail_space(s[::-1])[::-1]

        pf, ps, s = 0, 0, s[::-1] # Reverse the string.
        while pf < len(s):
            if s[pf] == " ":
                # Will not excede. Because we have clean the tail space.
                if s[pf] == s[pf + 1]:
                    s = s[:pf] + s[pf + 1:]
                    continue
                else:
                    s = s[:ps] + s[ps: pf][::-1] + s[pf:]
                    ps, pf = pf + 1, pf + 2
            else:
                pf += 1
        return s[:ps] + s[ps:][::-1] # Must do the last step, because the last word is omit though the pointers are on the correct positions,

Go：

import (
	"fmt"
)

func reverseWords(s string) string {
	//1.使用雙指針刪除冗余的空格
	slowIndex, fastIndex := 0, 0
	b := []byte(s)
	//刪除頭部冗余空格
	for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' {
		fastIndex++
	}
    //刪除單詞間冗余空格
	for ; fastIndex < len(b); fastIndex++ {
		if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' {
			continue
		}
		b[slowIndex] = b[fastIndex]
		slowIndex++
	}
	//刪除尾部冗余空格
	if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {
		b = b[:slowIndex-1]
	} else {
		b = b[:slowIndex]
	}
	//2.反轉(zhuǎn)整個字符串
	reverse(&b, 0, len(b)-1)
	//3.反轉(zhuǎn)單個單詞  i單詞開始位置，j單詞結(jié)束位置
	i := 0
	for i < len(b) {
		j := i
		for ; j < len(b) && b[j] != ' '; j++ {
		}
		reverse(&b, i, j-1)
		i = j
		i++
	}
	return string(b)
}

func reverse(b *[]byte, left, right int) {
	for left < right {
		(*b)[left], (*b)[right] = (*b)[right], (*b)[left]
		left++
		right--
	}
}

javaScript:

/**
 * @param {string} s
 * @return {string}
 */
 var reverseWords = function(s) {
   // 字符串轉(zhuǎn)數(shù)組
   const strArr = Array.from(s);
   // 移除多余空格
   removeExtraSpaces(strArr);
   // 翻轉(zhuǎn)
   reverse(strArr, 0, strArr.length - 1);

   let start = 0;

   for(let i = 0; i <= strArr.length; i++) {
     if (strArr[i] === ' ' || i === strArr.length) {
       // 翻轉(zhuǎn)單詞
       reverse(strArr, start, i - 1);
       start = i + 1;
     }
   }

   return strArr.join('');
};

// 刪除多余空格
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while(fastIndex < strArr.length) {
    // 移除開始位置和重復(fù)的空格
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}

// 翻轉(zhuǎn)從 start 到 end 的字符
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while(left < right) {
    // 交換
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}

TypeScript：

function reverseWords(s: string): string {
    /** Utils **/
    // 刪除多余空格, 如'   hello     world   ' => 'hello world'
    function delExtraSpace(arr: string[]): void {
        let left: number = 0,
            right: number = 0,
            length: number = arr.length;
        while (right < length && arr[right] === ' ') {
            right++;
        }
        while (right < length) {
            if (arr[right] === ' ' && arr[right - 1] === ' ') {
                right++;
                continue;
            }
            arr[left++] = arr[right++];
        }
        if (arr[left - 1] === ' ') {
            arr.length = left - 1;
        } else {
            arr.length = left;
        }
    }
    // 翻轉(zhuǎn)字符串，如：'hello' => 'olleh'
    function reverseWords(strArr: string[], start: number, end: number) {
        let temp: string;
        while (start < end) {
            temp = strArr[start];
            strArr[start] = strArr[end];
            strArr[end] = temp;
            start++;
            end--;
        }
    }

    /** Main code **/
    let strArr: string[] = s.split('');
    delExtraSpace(strArr);
    let length: number = strArr.length;
    // 翻轉(zhuǎn)整個字符串
    reverseWords(strArr, 0, length - 1);
    let start: number = 0,
        end: number = 0;
    while (start < length) {
        end = start;
        while (strArr[end] !== ' ' && end < length) {
            end++;
        }
        // 翻轉(zhuǎn)單個單詞
        reverseWords(strArr, start, end - 1);
        start = end + 1;
    }
    return strArr.join('');
};

Swift:

func reverseWords(_ s: String) -> String {
    var stringArr = removeSpace(s)
    reverseString(&stringArr, startIndex: 0, endIndex: stringArr.count - 1)
    reverseWord(&stringArr)
    return String(stringArr)
}

/// 1、移除多余的空格（前后所有的空格，中間只留一個空格）
func removeSpace(_ s: String) -> [Character] {
    let ch = Array(s)
    var left = 0
    var right = ch.count - 1
    // 忽略字符串前面的所有空格
    while ch[left] == " " {
        left += 1
    }
    // 忽略字符串后面的所有空格
    while ch[right] == " " {
        right -= 1
    }

    // 接下來就是要處理中間的多余空格
    var lastArr = Array<Character>()
    while left <= right {
        // 準(zhǔn)備加到新字符串當(dāng)中的字符
        let char = ch[left]
        // 新的字符串的最后一個字符；或者原字符串中，準(zhǔn)備加到新字符串的那個字符；這兩個字符當(dāng)中，只要有一個不是空格，就可以加到新的字符串當(dāng)中
        if char != " " || lastArr[lastArr.count - 1] != " "  {
            lastArr.append(char)
        }
      
        left += 1
    }
    return lastArr
}

/// 2、反轉(zhuǎn)整個字符串
func reverseString(_ s: inout [Character], startIndex: Int, endIndex: Int)  {
    var start = startIndex
    var end = endIndex
    while start < end {
        (s[start], s[end]) = (s[end], s[start])
        start += 1
        end -= 1
    }
}

/// 3、再次將字符串里面的單詞反轉(zhuǎn)
func reverseWord(_ s: inout [Character]) {
    var start = 0
    var end = 0
    var entry = false

    for i in 0..<s.count {
        if !entry {
            start = i
            entry = true
        }
      
        if entry && s[i] == " " && s[i - 1] != " " {
            end = i - 1
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }

        if entry && (i == s.count - 1) && s[i] != " " {
            end = i
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }
    }
}

Scala:

object Solution {
  def reverseWords(s: String): String = {
    var sb = removeSpace(s) // 移除多余的空格
    reverseString(sb, 0, sb.length - 1) // 翻轉(zhuǎn)字符串
    reverseEachWord(sb)
    sb.mkString
  }

  // 移除多余的空格
  def removeSpace(s: String): Array[Char] = {
    var start = 0
    var end = s.length - 1
    // 移除字符串前面的空格
    while (start < s.length && s(start) == ' ') start += 1
    // 移除字符串后面的空格
    while (end >= 0 && s(end) == ' ') end -= 1
    var sb = "" // String
    // 當(dāng)start小于等于end的時候，執(zhí)行添加操作
    while (start <= end) {
      var c = s(start)
      // 當(dāng)前字符不等于空，sb的最后一個字符不等于空的時候添加到sb
      if (c != ' ' || sb(sb.length - 1) != ' ') {
        sb ++= c.toString
      }
      start += 1 // 指針向右移動
    }
    sb.toArray
  }

  // 翻轉(zhuǎn)字符串
  def reverseString(s: Array[Char], start: Int, end: Int): Unit = {
    var (left, right) = (start, end)
    while (left < right) {
      var tmp = s(left)
      s(left) = s(right)
      s(right) = tmp
      left += 1
      right -= 1
    }
  }

  // 翻轉(zhuǎn)每個單詞
  def reverseEachWord(s: Array[Char]): Unit = {
    var i = 0
    while (i < s.length) {
      var j = i + 1
      // 向后迭代尋找每個單詞的坐標(biāo)
      while (j < s.length && s(j) != ' ') j += 1
      reverseString(s, i, j - 1)  // 翻轉(zhuǎn)每個單詞
      i = j + 1   // i往后更新
    }
  }
}

PHP:

function reverseWords($s) {
    $this->removeExtraSpaces($s); 
    $this->reverseString($s, 0, strlen($s)-1);
    // 將每個單詞反轉(zhuǎn)
    $start = 0; 
    for ($i = 0; $i <= strlen($s); $i++) {
        // 到達(dá)空格或者串尾，說明一個單詞結(jié)束。進(jìn)行翻轉(zhuǎn)。
        if ($i == strlen($s) || $s[$i] == ' ') { 
            // 翻轉(zhuǎn)，注意是左閉右閉 []的翻轉(zhuǎn)。
            $this->reverseString($s, $start, $i-1);
            // +1: 單詞與單詞直接有個空格
            $start = $i + 1; 
        }
    }
    return $s;
}

// 移除多余空格
function removeExtraSpaces(&$s){
    $slow = 0;   
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] != ' ') { 
            if ($slow != 0){
                $s[$slow++] = ' ';
            } 
            while ($i < strlen($s) && $s[$i] != ' ') { 
                $s[$slow++] = $s[$i++];
            }
        }
    }
    // 移動覆蓋處理，丟棄多余的臟數(shù)據(jù)。
    $s = substr($s,0,$slow);
    return ;
}

// 翻轉(zhuǎn)字符串
function reverseString(&$s, $start, $end) {
    for ($i = $start, $j = $end; $i < $j; $i++, $j--) {
        $tmp = $s[$i];
        $s[$i] = $s[$j];
        $s[$j] = $tmp;
    }
    return ;
}

Rust:文章來源地址http://www.zghlxwxcb.cn/news/detail-489766.html

// 根據(jù)C++版本二思路進(jìn)行實(shí)現(xiàn)
// 函數(shù)名根據(jù)Rust編譯器建議由駝峰命名法改為蛇形命名法
impl Solution {
    pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
        while begin < end {
            let temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            begin += 1;
            end -= 1;
        }
}
pub fn remove_extra_spaces(s: &mut Vec<char>) {
        let mut slow: usize = 0;
        let len = s.len();
        // 注意這里不能用for循環(huán)，不然在里面那個while循環(huán)中對i的遞增會失效
        let mut i: usize = 0;
        while i < len {
            if !s[i].is_ascii_whitespace() {
                if slow != 0 {
                    s[slow] = ' ';
                    slow += 1;
                }
                while i < len && !s[i].is_ascii_whitespace() {
                    s[slow] = s[i];
                    slow += 1;
                    i += 1;
                }
            }
            i += 1;
        }
        s.resize(slow, ' ');
    }
    pub fn reverse_words(s: String) -> String {
        let mut s = s.chars().collect::<Vec<char>>();
        Self::remove_extra_spaces(&mut s);
        let len = s.len();
        Self::reverse(&mut s, 0, len - 1);
        let mut start = 0;
        for i in 0..=len {
            if i == len || s[i].is_ascii_whitespace() {
                Self::reverse(&mut s, start, i - 1);
                start = i + 1;
            }
        }
        s.iter().collect::<String>()
    }
}

到了這里，關(guān)于算法刷題-字符串-翻轉(zhuǎn)字符串里的單詞的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！