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题目的分析，我们可以看到字符串问题的解法通常涉及到双指针、哈希表、字符统计等技巧。掌握这些基本技巧，能够帮助我们更高效地解决字符串相关的算法问题。在实际编程中，理解问题的本质并选择合适的算法是解决问题的关键。