如何使用LeetCode反轉字符串

如何使用LeetCode反轉字符串

在編程面試中，字符串操作是一個常見的考察點。反轉字符串是其中最基本的問題之一，也是理解字符串操作和指針/索引操作的好方法。本文將介紹如何在LeetCode上解決反轉字符串問題，并提供詳細的代碼示例和解釋。

問題描述

LeetCode上的反轉字符串問題通常描述如下：

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。

不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。

解題思路

反轉字符串的基本思路是交換字符串的首尾字符，然后逐步向中間移動，直到整個字符串被反轉。具體步驟如下：

1. 初始化兩個指針，一個指向字符串的開頭（left），另一個指向字符串的末尾（right）。
2. 交換 left 和 right 指針所指向的字符。
3. 將 left 指針向右移動一位，將 right 指針向左移動一位。
4. 重復步驟2和3，直到 left 指針不再小于 right 指針。

這種方法的時間復雜度是 O(n)，其中 n 是字符串的長度。由于我們只使用了常數級別的額外空間，空間復雜度是 O(1)。

代碼實現

以下是使用Python語言實現的代碼：

def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

代碼解釋

1. 初始化指針：我們首先定義兩個指針 left 和 right，分別指向字符串的開頭和末尾。
2. 交換字符：在 while 循環中，我們交換 left 和 right 指針所指向的字符。Python中的交換操作非常簡潔，可以直接使用 s[left], s[right] = s[right], s[left]。
3. 移動指針：交換完成后，我們將 left 指針向右移動一位，將 right 指針向左移動一位。
4. 循環終止條件：當 left 指針不再小于 right 指針時，循環終止，此時字符串已經被完全反轉。

測試用例

為了驗證我們的代碼是否正確，我們可以編寫一些測試用例：

# 測試用例1
s1 = ["h","e","l","l","o"]
reverseString(s1)
print(s1)  # 輸出: ["o","l","l","e","h"]

# 測試用例2
s2 = ["H","a","n","n","a","h"]
reverseString(s2)
print(s2)  # 輸出: ["h","a","n","n","a","H"]

# 測試用例3
s3 = ["a"]
reverseString(s3)
print(s3)  # 輸出: ["a"]

# 測試用例4
s4 = ["A"," ","m","a","n",","," ","a"," ","p","l","a","n",","," ","a"," ","c","a","n","a","l",":"," ","P","a","n","a","m","a"]
reverseString(s4)
print(s4)  # 輸出: ["a","m","a","n","a","P"," ",":","l","a","n","a","c"," ","a"," ",",","n","a","l","p"," ","a"," ",",","n","a","m"," ","A"]

復雜度分析

• 時間復雜度：O(n)，其中 n 是字符串的長度。我們需要遍歷字符串的一半長度來完成反轉操作。
• 空間復雜度：O(1)，我們只使用了常數級別的額外空間。

總結

反轉字符串是一個經典的編程問題，通過使用雙指針技巧，我們可以高效地解決這個問題。在LeetCode上，這個問題不僅考察了基本的字符串操作，還考察了原地修改數組的能力。掌握這個問題的解法，不僅有助于通過面試，還能加深對指針和數組操作的理解。

希望本文對你理解如何使用LeetCode反轉字符串有所幫助。如果你有任何問題或建議，歡迎在評論區留言討論。