Last Updated on 2022-04-01 by Clay
題目
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Constraints:
1 <= s.length <= 105s[i]is a printable ascii character.
題目輸入一組字元陣列（character array），我們反轉整個陣列的順序。不需要回傳。
解題思路
語言內建函式解法
解釋一下，我將刷 LeetCode 視為工作面試，我會提出使用解題語言的內建函式來解題，以證明我對這個程式語言有最基本的熟悉度。
不過當然如果只提出這種解法的話，訓練解題就稍微有點沒意義了。
語言內建函式解法複雜度
內建函式的時間複雜度為 O(n)。合理。
| Time complexity | O(n) |
| Space complexity | O(1) |
語言內建函式解法 C++ 範例程式碼
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(), s.end());
}
};語言內建函式解法 Python 範例程式碼
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
兩端點解法
另一個很直覺的解法，就是分別令左右端點，然後交換左右端點的值，接著左端點加一、右端點減一...... 以此循環直到左端點跟右端點相遇（或左端點大於右端點，代表陣列遍歷完成）。
順帶一提，左右端點相遇時就不用交換了，因為兩個指向同個字元。
兩端點解法複雜度
由於我們需要遍歷整個陣列，故時間複雜度為 O(n)。
| Time complexity | O(n) |
| Space complexity | O(1) |
兩端點解法 C++ 範例程式碼
class Solution {
public:
void reverseString(vector<char>& s) {
// Init
int left = 0;
int right = s.size() - 1;
// Exchange
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
++left;
--right;
}
}
};兩端點解法 Python 範例程式碼
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# Init
left = 0
right = len(s) - 1
# Exchange
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1