LeetCode中字符串的示例分析

LeetCode中字符串的示例分析

在LeetCode的算法題庫中，字符串相關的題目占據了相當大的比例。字符串作為一種基本的數據結構，廣泛應用于各種算法問題中。本文將通過幾個典型的LeetCode題目，分析字符串問題的常見解法與技巧。

1. 字符串反轉

題目：反轉字符串（LeetCode 344）

題目描述：編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

示例：

輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]

分析： 這是一個經典的字符串反轉問題。由于要求原地修改數組，我們可以使用雙指針技巧。定義兩個指針，一個指向字符串的開頭，另一個指向字符串的末尾，然后交換這兩個指針所指向的字符，逐步向中間移動指針，直到兩個指針相遇。

代碼實現：

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

時間復雜度：O(n)，其中 n 是字符串的長度。每個字符被交換一次。

2. 字符串中的第一個唯一字符

題目：字符串中的第一個唯一字符（LeetCode 387）

題目描述：給定一個字符串，找到它的第一個不重復的字符，并返回它的索引。如果不存在，則返回 -1。

示例：

輸入: "leetcode"
輸出: 0

分析： 要找到第一個不重復的字符，我們可以使用哈希表來記錄每個字符出現的次數。首先遍歷字符串，統計每個字符的出現次數。然后再次遍歷字符串，找到第一個出現次數為1的字符，并返回其索引。

代碼實現：

def firstUniqChar(s):
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for i, char in enumerate(s):
        if count[char] == 1:
            return i
    return -1

時間復雜度：O(n)，其中 n 是字符串的長度。我們遍歷了字符串兩次。

3. 有效的字母異位詞

題目：有效的字母異位詞（LeetCode 242）

題目描述：給定兩個字符串 s 和 t，編寫一個函數來判斷 t 是否是 s 的字母異位詞。

示例：

輸入: s = "anagram", t = "nagaram"
輸出: true

分析： 字母異位詞是指由相同字母重新排列形成的單詞。我們可以通過統計每個字符的出現次數來判斷兩個字符串是否是字母異位詞。如果兩個字符串中每個字符的出現次數都相同，則它們是字母異位詞。

代碼實現：

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for char in s:
        count[ord(char) - ord('a')] += 1
    for char in t:
        count[ord(char) - ord('a')] -= 1
    for c in count:
        if c != 0:
            return False
    return True

時間復雜度：O(n)，其中 n 是字符串的長度。我們遍歷了兩個字符串各一次，并且遍歷了一個固定長度的數組。

4. 最長公共前綴

題目：最長公共前綴（LeetCode 14）

題目描述：編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

示例：

輸入: ["flower","flow","flight"]
輸出: "fl"

分析： 要找到多個字符串的最長公共前綴，我們可以逐個字符比較所有字符串。首先找到最短的字符串，然后依次比較每個字符，直到出現不匹配的字符為止。

代碼實現：

def longestCommonPrefix(strs):
    if not strs:
        return ""
    shortest = min(strs, key=len)
    for i, char in enumerate(shortest):
        for other in strs:
            if other[i] != char:
                return shortest[:i]
    return shortest

時間復雜度：O(S)，其中 S 是所有字符串中字符的總數。最壞情況下，我們需要比較所有字符串的每個字符。

5. 字符串轉換整數 (atoi)

題目：字符串轉換整數 (atoi)（LeetCode 8）

題目描述：請你來實現一個 atoi 函數，使其能將字符串轉換成整數。

示例：

輸入: "   -42"
輸出: -42

分析： 這個問題需要考慮多種邊界情況，如空格、正負號、非數字字符等。我們可以通過逐個字符處理字符串，逐步構建整數。

代碼實現：

def myAtoi(s):
    s = s.strip()
    if not s:
        return 0
    sign = -1 if s[0] == '-' else 1
    if s[0] in ['-', '+']:
        s = s[1:]
    res = 0
    for char in s:
        if not char.isdigit():
            break
        res = res * 10 + int(char)
    res = sign * res
    res = max(min(res, 2**31 - 1), -2**31)
    return res

時間復雜度：O(n)，其中 n 是字符串的長度。我們只遍歷了字符串一次。

總結

通過以上幾個LeetCode題目的分析，我們可以看到字符串問題的解法通常涉及到雙指針、哈希表、字符統計等技巧。掌握這些基本技巧，能夠幫助我們更高效地解決字符串相關的算法問題。在實際編程中，理解問題的本質并選擇合適的算法是解決問題的關鍵。