186. Reverse Words in a String II
給定一個字符數組 s，反轉單詞的順序。
單詞被定義為一個非空格字符的序列。字符數組中的單詞將由單個空格分隔。
你的代碼必須原地解決這個問題，即不能分配額外的空間。
範例：
輸入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
輸出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
輸入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
輸出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Python
from typing import List
class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# Helper function to reverse the characters in the array from index left to right
def reverse(left: int, right: int) -> None:
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
# Step 1: Reverse the entire array
reverse(0, len(s) - 1)
# Step 2: Reverse each word in the array
start = 0
for end in range(len(s)):
if s[end] == ' ':
reverse(start, end - 1)
start = end + 1
# Reverse the last word
reverse(start, len(s) - 1)
20.53MB, 187ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void reverseWords(vector<char>& s) {
// Helper function to reverse a portion of the vector
auto reverse = [&](int left, int right) {
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
};
// Step 1: Reverse the entire vector
reverse(0, s.size() - 1);
// Step 2: Reverse each word
int start = 0;
for (int end = 0; end <= s.size(); ++end) {
if (end == s.size() || s[end] == ' ') {
reverse(start, end - 1);
start = end + 1;
}
}
}
};
20.03MB, 7ms
Javascript
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseWords = function(s) {
// Helper function to reverse characters in the array from index left to right
const reverse = (left, right) => {
while (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
};
// Step 1: Reverse the entire array
reverse(0, s.length - 1);
// Step 2: Reverse each word in the array
let start = 0;
for (let end = 0; end <= s.length; end++) {
if (end === s.length || s[end] === ' ') {
reverse(start, end - 1);
start = end + 1;
}
}
};
58.55MB, 78ms
