第一题、709.转换成小写字母
方法一：使用语言 API
class Solution:
def toLowerCase(self, s: str) -> str:
return s.lower()
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)，不考虑返回值的空间占用。
方法二、自行实现该 API
class Solution:
def toLowerCase(self, s: str) -> str:
return "".join(chr(asc | 32) if 65 <= (asc := ord(ch)) <= 90 else ch for ch in s)
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)，不考虑返回值的空间占用。
第二题、58.最后一个单词的长度
方法一：反向遍历
题目要求得到字符串中最后一个单词的长度，可以反向遍历字符串，寻找最后一个单词并计算其长度。
由于字符串中至少存在一个单词，因此字符串中一定有字母。首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。
从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。
class Solution:
def lengthOfLastWord(self, s: str) -> int:
# 从字符串的末尾开始遍历
index = len(s) - 1
# 跳过末尾的空格
while index >= 0 and s[index] == ' ':
index -= 1
word_length = 0 # 初始化单词长度为0
# 继续向前遍历，直到遇到空格或到达字符串开头
while index >= 0 and s[index] != ' ':
word_length += 1 # 增加单词长度
index -= 1 # 向前移动一位
return word_length # 返回最后一个单词的长度
时间复杂度：O(n)，其中 n 是字符串的长度。最多需要反向遍历字符串一次。
空间复杂度：O(1)。
第三题、771.宝石与石头
方法一、暴力
遍历字符串 stones，对于 stones 中的每个字符，遍历一次字符串 jewels，如果其和 jewels 中的某一个字符相同，则是宝石。
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
return sum(s in jewels for s in stones)
时间复杂度：O(mn)，其中 m 是字符串 jewels 的长度，n 是字符串 stones 的长度。遍历字符串 stones 的时间复杂度是 O(n)，对于 stones 中的每个字符，需要遍历字符串 jewels 判断是否是宝石，时间复杂度是 O(m)，因此总时间复杂度是 O(mn)。
空间复杂度：O(1)。只需要维护常量的额外空间。
方法二、哈希集合
方法一中，对于字符串 stones 中的每个字符，都需要遍历一次字符串 jewels，导致时间复杂度较高。如果使用哈希集合存储字符串 jewels 中的宝石，则可以降低判断的时间复杂度。
遍历字符串 jewels，使用哈希集合存储其中的字符，然后遍历字符串 stones，对于其中的每个字符，如果其在哈希集合中，则是宝石。
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
jewelsSet = set(jewels)
return sum(s in jewelsSet for s in stones)
时间复杂度：O(m+n)，其中 m 是字符串 jewels 的长度，n 是字符串 stones 的长度。遍历字符串 jewels 将其中的字符存储到哈希集合中，时间复杂度是 O(m)，然后遍历字符串 stones，对于 stones 中的每个字符在 O(1) 的时间内判断当前字符是否是宝石，时间复杂度是 O(n)，因此总时间复杂度是 O(m+n)。
空间复杂度：O(m)，其中 m 是字符串 jewels 的长度。使用哈希集合存储字符串 jewels 中的字符。
第四题、387.字符串中的第一个唯一字符
方法一：使用哈希表存储频数
对字符串进行两次遍历。在第一次遍历时，使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 −1。
class Solution:
def firstUniqChar(self, s: str) -> int:
frequency = collections.Counter(s)
for i, ch in enumerate(s):
if frequency[ch] == 1:
return i
return -1
时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要进行两次遍历。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。需要 O(∣Σ∣) 的空间存储哈希映射。
方法二：使用哈希表存储索引
可以对方法一进行修改，使得第二次遍历的对象从字符串变为哈希映射。
具体地，对于哈希映射中的每一个键值对，键表示一个字符，值表示它的首次出现的索引（如果该字符只出现一次）或者 −1（如果该字符出现多次）。当第一次遍历字符串时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，就将 c 与它的索引作为一个键值对加入哈希映射中，否则将 c 在哈希映射中对应的值修改为 −1。
在第一次遍历结束后，只需要再遍历一次哈希映射中的所有值，找出其中不为 −1 的最小值，即为第一个不重复字符的索引。如果哈希映射中的所有值均为 −1，就返回 −1。
class Solution:
def firstUniqChar(self, s: str) -> int:
# 创建一个字典来存储每个字符最后出现的位置，初始为空
position = dict()
n = len(s) # 获取字符串s的长度
# 遍历字符串s中的每个字符及其索引
for i, ch in enumerate(s):
# 如果字符ch已经在字典中，则将其值设置为-1（表示该字符不是唯一的）
if ch in position:
position[ch] = -1
else:
# 如果字符ch不在字典中，则将其添加到字典中，并记录其索引位置
position[ch] = i
# 初始化first为字符串s的长度（一个较大的值，用于后续比较）
first = n
# 遍历字典中的所有值（即字符最后出现的位置）
for pos in position.values():
# 如果位置不是-1（即该字符是唯一的），并且这个位置比之前记录的第一个唯一字符的位置更小
if pos != -1 and pos < first:
# 更新first为当前找到的更小的位置
first = pos
# 如果first仍然是字符串s的长度（即没有找到任何唯一字符），则将first设置为-1
if first == n:
first = -1
# 返回第一个唯一字符的索引位置，如果没有找到，则返回-1
return first
时间复杂度：O(n)，其中 n 是字符串 s 的长度。第一次遍历字符串的时间复杂度为 O(n)，第二次遍历哈希映射的时间复杂度为 O(∣Σ∣)，由于 s 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。需要 O(∣Σ∣) 的空间存储哈希映射。
我的疑问：
为什么 if pos != -1 and pos < first: 这个判断条件中要加 pos < first？ 在position字典中第一个出现的值不等于-1的字符所对应的索引下标一定是最小的呀？
解答：
position 字典用于存储每个字符在字符串 s 中最后出现的位置。然而，position 字典并不保证按照字符在字符串中出现的顺序来存储键值对。Python 字典是无序的（在 Python 3.7 之前的版本中是这样，尽管在 3.7+ 中字典保持插入顺序，但在这个上下文中关注的是“最后出现的位置”，而不是插入顺序）。
因此，当遍历 position.values() 时，得到的是一个包含所有字符最后出现位置的值的列表，但这个列表并不是按照字符在字符串中首次出现的顺序排序的。这就是为什么需要 if pos != -1 and pos < first: 这个判断条件。
pos != -1：这个条件用于检查当前字符是否是唯一的（即它在字符串中只出现了一次）。如果 pos 是 -1，则表示该字符在字符串中出现了不止一次，因此它不是要找的第一个唯一字符。
pos < first：这个条件用于确保找到的字符位置比之前记录的任何唯一字符的位置都要早。这是因为要找的是第一个出现的唯一字符。如果不检查 pos < first，那么当遍历到后面的字符时，即使它们是唯一的，但如果它们的位置不是最早的，也不会更新 first 变量。
因此，pos < first 是必要的，以确保只记录并返回第一个出现的唯一字符的位置。
总结一下，position 字典中的值（即字符最后出现的位置）并不保证按照字符在字符串中首次出现的顺序来排序，所以需要使用 pos < first 来确保找到的是第一个出现的唯一字符。
明白了上述我的疑问后，我会想到是否可以优化数据结构？方法三就是对这个的优化。
方法三：队列
可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。
使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，就将 c 与它的索引作为一个二元组放入队尾，否则就需要检查队列中的元素是否都满足「只出现一次」的要求，即不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。
在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。
在维护队列时，使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，才需要将它移除。
from collections import deque # 导入deque，用于实现双端队列
class Solution:
def firstUniqChar(self, s: str) -> int:
# 创建一个字典来存储每个字符最后出现的位置
position = dict()
# 创建一个双端队列，用于存储字符及其索引，以便快速访问第一个唯一字符的索引
q = deque()
n = len(s) # 获取字符串s的长度
# 遍历字符串s中的每个字符及其索引
for i, ch in enumerate(s):
# 如果字符ch不在position字典中，表示这是该字符第一次出现
if ch not in position:
position[ch] = i # 记录该字符最后出现的位置
q.append((ch, i)) # 将字符及其索引添加到队列中
else:
# 如果字符ch已经在position字典中，表示该字符不是唯一的
position[ch] = -1 # 更新该字符的位置为-1，表示它不是唯一的
# 从队列头部移除所有已经不再是唯一的字符（即position值为-1的字符）
while q and position[q[0][0]] == -1:
q.popleft()
# 如果队列为空，表示没有找到唯一字符，返回-1
# 否则，返回队列头部元素（即第一个唯一字符）的索引
return -1 if not q else q[0][1]
时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串的时间复杂度为 O(n)，而在遍历的过程中还维护了一个队列，由于每一个字符最多只会被放入和弹出队列最多各一次，因此维护队列的总时间复杂度为 O(∣Σ∣)，由于 s 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。需要 O(∣Σ∣) 的空间存储哈希映射以及队列。
第五题、8.字符串转换整数(atoi)
思路、自动机
字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。
因此，为了有条理地分析每个输入字符的处理方法，可以使用自动机这个概念：
程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。这样，只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题。
# 定义INT_MAX和INT_MIN，表示32位有符号整数的最大值和最小值
INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31
class Automaton:
def __init__(self):
# 初始化状态为'start'，表示开始状态
self.state = 'start'
# 初始化符号为正，默认为正数
self.sign = 1
# 初始化答案为0
self.ans = 0
# 定义状态转移表，根据当前状态和输入字符的类别决定下一个状态
self.table = {
'start': ['start', 'signed', 'in_number', 'end'], # 开始状态
'signed': ['end', 'end', 'in_number', 'end'], # 已识别符号状态
'in_number': ['end', 'end', 'in_number', 'end'], # 正在处理数字状态
'end': ['end', 'end', 'end', 'end'], # 结束状态
}
def get_col(self, c):
# 根据字符c的类型返回对应的列索引
if c.isspace():
return 0 # 空格
if c == '+' or c == '-':
return 1 # 正负号
if c.isdigit():
return 2 # 数字
return 3 # 其他字符
def get(self, c):
# 根据当前状态和字符c更新状态
self.state = self.table[self.state][self.get_col(c)]
# 如果当前状态为'in_number'，则处理数字
if self.state == 'in_number':
self.ans = self.ans * 10 + int(c)
# 根据符号和当前值更新答案，确保不超过INT_MAX或INT_MIN
self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
# 如果当前状态为'signed'，则设置符号
elif self.state == 'signed':
self.sign = 1 if c == '+' else -1
class Solution:
def myAtoi(self, str: str) -> int:
# 创建自动机实例
automaton = Automaton()
# 遍历字符串中的每个字符
for c in str:
automaton.get(c)
# 返回根据符号和答案计算出的最终结果
return automaton.sign * automaton.ans
时间复杂度：O(n)，其中 n 为字符串的长度。只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。
空间复杂度：O(1)。自动机的状态只需要常数空间存储。
第六题、14.最长公共前缀
方法一、横向扫描
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 如果字符串列表为空，则最长公共前缀为空字符串
if not strs:
return ""
# 初始化最长公共前缀为列表中的第一个字符串，并获取列表中字符串的数量
prefix, count = strs[0], len(strs)
# 遍历列表中的每一个字符串（从第二个开始）
for i in range(1, count):
# 计算当前字符串与前一个最长公共前缀的公共前缀
prefix = self.lcp(prefix, strs[i])
# 如果公共前缀为空，则直接结束循环，因为后续字符串也不可能有更长的公共前缀
if not prefix:
break
# 返回最终的最长公共前缀
return prefix
def lcp(self, str1, str2):
# 获取两个字符串中较短的长度，以及初始化索引为0
length, index = min(len(str1), len(str2)), 0
# 遍历两个字符串，直到任一字符串结束或当前位置的字符不相等
while index < length and str1[index] == str2[index]:
index += 1
# 返回从字符串开头到找到的不相等字符位置之前的子字符串（即公共前缀）
return str1[:index]
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
方法二、纵向扫描
方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 如果字符串列表为空，则最长公共前缀为空字符串
if not strs:
return ""
# 初始化最长公共前缀的长度为列表中第一个字符串的长度
# 同时获取列表中字符串的数量
length, count = len(strs[0]), len(strs)
# 遍历第一个字符串的每一个字符
for i in range(length):
# 获取当前遍历到的字符
c = strs[0][i]
# 使用any函数检查列表中除第一个字符串外的其他字符串
# 是否存在当前索引超出字符串长度或当前索引位置的字符与c不相等的情况
# 如果存在，则返回当前已确定的最长公共前缀（即strs[0][:i]）
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
return strs[0][:i]
# 如果遍历完第一个字符串的所有字符都没有发现不符合条件的情况
# 则说明第一个字符串就是最长公共前缀（或所有字符串都相同）
return strs[0]
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
方法三、分治
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 定义一个内部函数lcp，用于递归地找到最长公共前缀
# 参数start和end分别表示当前考虑的字符串列表的起始和结束索引
def lcp(start, end):
# 如果起始索引等于结束索引，说明当前考虑的只有一个字符串，直接返回该字符串
if start == end:
return strs[start]
# 计算中间索引
mid = (start + end) // 2
# 递归地找到左半部分和右半部分的最长公共前缀
lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
# 获取左右两部分最长公共前缀的较短长度
minLength = min(len(lcpLeft), len(lcpRight))
# 遍历较短长度的部分，检查左右两部分对应位置的字符是否相同
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
# 如果发现不同，则返回左部分的最长公共前缀中直到当前位置的部分
return lcpLeft[:i]
# 如果遍历完较短长度的部分都没有发现不同，则返回左部分的最长公共前缀中直到较短长度的部分
return lcpLeft[:minLength]
# 检查字符串列表是否为空，如果为空则返回空字符串
# 如果不为空，则调用lcp函数计算并返回最长公共前缀
return "" if not strs else lcp(0, len(strs) - 1)
方法四、二分查找
最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# 定义一个辅助函数，用于检查给定长度的前缀是否是所有字符串的公共前缀
def isCommonPrefix(length):
# 取第一个字符串的前length个字符作为基准
str0, count = strs[0][:length], len(strs)
# 使用all函数和生成器表达式检查每个字符串的前length个字符是否与基准相同
return all(strs[i][:length] == str0 for i in range(1, count))
# 如果字符串列表为空，则没有公共前缀，返回空字符串
if not strs:
return ""
# 找到字符串列表中最短字符串的长度，因为最长公共前缀的长度不会超过最短字符串的长度
minLength = min(len(s) for s in strs)
# 使用二分查找的思想来找到最长公共前缀的长度
low, high = 0, minLength
# 当low小于high时，循环继续
while low < high:
# 计算中点，注意这里使用(high - low + 1) // 2 + low是为了处理high和low相差不大的情况，避免死循环
mid = (high - low + 1) // 2 + low
# 检查当前中点长度的前缀是否是所有字符串的公共前缀
if isCommonPrefix(mid):
# 如果是，则调整low的值，继续在右半部分搜索可能更长的公共前缀
low = mid
else:
# 如果不是，则调整high的值，在左半部分继续搜索
high = mid - 1
# 当low和high相等时，循环结束，此时low（或high）指向的就是最长公共前缀的长度
# 返回第一个字符串的前low个字符作为最长公共前缀
return strs[0][:low]
时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
第七题、344.反转字符串
方法、双指针
对于长度为 N 的待被反转的字符数组，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此可以得出如下双指针的解法：
将 left 指向字符数组首元素，right 指向字符数组尾元素。
当 left < right：
交换 s[left] 和 s[right]；
left 指针右移一位，即 left = left + 1；
right 指针左移一位，即 right = right - 1。
当 left >= right，反转结束，返回字符数组即可。
class Solution:
def reverseString(self, s: List[str]) -> None:
n = len(s) # 获取列表s的长度
left, right = 0, n - 1 # 初始化左指针和右指针
while left < right: # 当左指针小于右指针时，执行循环
s[left], s[right] = s[right], s[left] # 交换左指针和右指针指向的元素
left += 1 # 左指针向右移动
right -= 1 # 右指针向左移动
时间复杂度：O(N)，其中 N 为字符数组的长度。一共执行了 N/2 次的交换。
空间复杂度：O(1)。只使用了常数空间来存放若干变量。
第八题、541.反转字符串2
方法、模拟
class Solution:
def reverseStr(self, s: str, k: int) -> str:
t = list(s)
for i in range(0, len(t), 2 * k):
t[i: i + k] = reversed(t[i: i + k])
return "".join(t)
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)
第九题、151.反转字符串中的单词
方法一、使用语言特性
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(reversed(s.split()))
时间复杂度：O(n)，其中 n 为输入字符串的长度。
空间复杂度：O(n)，用来存储字符串分割之后的结果。
方法二、自己编写对应的函数
Python是字符串不可变的语言，首先得把字符串转化成其他可变的数据结构，同时还需要在转化的过程中去除空格。
class Solution:
def trim_spaces(self, s: str) -> list:
left, right = 0, len(s) - 1 # 初始化左右指针
# 去掉字符串开头的空白字符
while left <= right and s[left] == ' ':
left += 1
# 去掉字符串末尾的空白字符
while left <= right and s[right] == ' ':
right -= 1
# 初始化输出列表，用于存储处理后的字符
output = []
# 遍历字符串，去除单词间多余的空白字符，并将非空白字符添加到输出列表
while left <= right:
if s[left] != ' ':
output.append(s[left])
elif output and output[-1] != ' ': # 确保不是列表的第一个元素且前一个元素不是空格
output.append(s[left])
left += 1
return output # 返回处理后的字符列表
def reverse(self, l: list, left: int, right: int) -> None:
# 翻转列表中的一部分元素
while left < right:
l[left], l[right] = l[right], l[left]
left, right = left + 1, right - 1
def reverse_each_word(self, l: list) -> None:
n = len(l)
start = end = 0
# 遍历列表，找到每个单词的起始和结束位置，并翻转每个单词
while start < n:
# 循环至单词的末尾（包括空格分隔符）
while end < n and l[end] != ' ':
end += 1
# 翻转单词（不包括末尾的空格）
self.reverse(l, start, end - 1)
# 更新start，去找下一个单词的起始位置
start = end + 1
end += 1
def reverseWords(self, s: str) -> str:
l = self.trim_spaces(s) # 去除字符串首尾的空格以及单词间的多余空格
# 翻转整个字符串（实际上是翻转字符列表）
self.reverse(l, 0, len(l) - 1)
# 翻转每个单词，恢复单词内部的顺序
self.reverse_each_word(l)
return ''.join(l) # 将处理后的字符列表转换回字符串并返回
时间复杂度：O(n)，其中 n 为输入字符串的长度。
空间复杂度：O(n) ，存储字符串。
方法三：双端队列
由于双端队列支持从队列头部插入的方法，因此可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。
class Solution:
def reverseWords(self, s: str) -> str:
left, right = 0, len(s) - 1 # 初始化左右指针
# 去掉字符串开头的空白字符
while left <= right and s[left] == ' ':
left += 1
# 去掉字符串末尾的空白字符
while left <= right and s[right] == ' ':
right -= 1
d = deque() # 创建一个 deque 对象，用于存储翻转后的单词
word = [] # 创建一个列表，用于临时存储当前单词的字符
# 遍历字符串，将单词 push 到队列的头部
while left <= right:
if s[left] == ' ' and word: # 如果遇到空格且 word 列表不为空，则将 word 列表中的字符连接成字符串并 push 到 deque 的头部
d.appendleft(''.join(word))
word = [] # 清空 word 列表，准备存储下一个单词
elif s[left] != ' ': # 如果不是空格，则将当前字符添加到 word 列表中
word.append(s[left])
left += 1 # 移动左指针
# 将最后一个单词（如果有的话）也 push 到 deque 的头部
if word:
d.appendleft(''.join(word))
# 将 deque 中的单词使用空格连接起来，并返回结果字符串
return ' '.join(d)
时间复杂度：O(n)，其中 n 为输入字符串的长度。
空间复杂度：O(n)，双端队列存储单词需要 O(n) 的空间。
第十题、557.反转字符串中的单词3
方法一：使用额外空间
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
class Solution:
def reverseWords(self, s: str) -> str:
# 初始化结果字符串
ret = []
# 获取输入字符串的长度
length = len(s)
# 初始化索引i，用于遍历字符串
i = 0
# 遍历字符串直到末尾
while i < length:
# 标记当前单词的起始位置
start = i
# 跳过当前单词的剩余部分（直到空格或字符串末尾）
while i < length and s[i] != ' ':
i += 1
# 反转当前单词，并添加到结果列表中
# 注意：Python中的字符串是不可变的，所以先将单词切片出来，再反转
word = s[start:i][::-1]
ret.append(word)
# 跳过单词之间的空格（如果有的话）
while i < length and s[i] == ' ':
i += 1
# 使用空格将反转后的单词列表连接成一个字符串
# 注意：Python中的join方法需要一个字符串列表作为输入
return ' '.join(ret)
时间复杂度：O(N)，其中 N 为字符串的长度。原字符串中的每个字符都会在 O(1) 的时间内放入新字符串中。
空间复杂度：O(N)。开辟了与原字符串等大的空间。
方法二、原地解法
此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……如此反复，就可以在原空间上翻转单词。
需要注意的是，原地解法在某些语言（比如Python，Java）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
第十一题、917.仅仅反转字母
方法一：双指针
使用 left 指针从左边开始扫描字符串 s，right 指针从右边开始扫描字符串 s。如果两个指针都扫描到字母，且 left<right，那么交换 s[left] 和 s[right]，然后继续进行扫描；否则表明反转过程结束，返回处理后的字符串。
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
# 将输入字符串s转换为字符列表，以便我们可以修改其中的元素
ans = list(s)
# 初始化两个指针，left指向字符串的开始，right指向字符串的末尾
left, right = 0, len(ans) - 1
# 使用while循环来持续寻找并交换字母，直到left >= right时退出循环
while True:
# 从左向右扫描，直到找到一个字母或left >= right
while left < right and not ans[left].isalpha(): # 判断左边是否扫描到字母
left += 1
# 从右向左扫描，直到找到一个字母或left >= right
while right > left and not ans[right].isalpha(): # 判断右边是否扫描到字母
right -= 1
# 如果left >= right，说明已经扫描完整个字符串，退出循环
if left >= right:
break
# 交换left和right指向的字符（仅当它们都是字母时）
ans[left], ans[right] = ans[right], ans[left]
# 移动指针，继续下一轮搜索
left += 1
right -= 1
# 使用join方法将字符列表转换回字符串，并返回结果
return ''.join(ans)
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n)。Python字符串不可变，需要 O(n) 的额外空间。
第十二题、125.验证回文串
方法一：筛选 + 判断
最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样只需要判断 sgood 是否是一个普通的回文串即可。
判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。
class Solution:
def isPalindrome(self, s: str) -> bool:
sgood = "".join(ch.lower() for ch in s if ch.isalnum())
return sgood == sgood[::-1]
第二种是使用双指针。初始时，左右指针分别指向 sgood 的两侧，随后不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 sgood 时回文串。
class Solution:
def isPalindrome(self, s: str) -> bool:
sgood = "".join(ch.lower() for ch in s if ch.isalnum())
n = len(sgood)
left, right = 0, n - 1
while left < right:
if sgood[left] != sgood[right]:
return False
left, right = left + 1, right - 1
return True
时间复杂度：O(∣s∣)，其中 ∣s∣ 是字符串 s 的长度。
空间复杂度：O(∣s∣)。由于需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串 sgood 与原字符串 s 完全相同，因此需要使用 O(∣s∣) 的空间。
疑问：isalnum()？
isalnum() 是 Python 中的一个字符串方法，用于检查字符串中的所有字符是否都是字母或数字。如果字符串中的所有字符都是字母或数字，则返回 True；否则返回 False。这个方法对于忽略字符串中的空白字符（如空格、制表符等）和特殊字符（如标点符号、符号等）特别有用，因为它只关注字母和数字字符。
isalnum() 方法不会改变原始字符串，它只是返回一个布尔值（True 或 False）来表示字符串是否只包含字母和数字。
方法二：在原字符串上直接判断
可以对方法一中第二种判断回文串的方法进行优化，就可以得到只使用 O(1) 空间的算法。
直接在原字符串 s 上使用双指针。在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。也就是说，每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。
class Solution:
def isPalindrome(self, s: str) -> bool:
n = len(s)
left, right = 0, n - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if left < right:
if s[left].lower() != s[right].lower():
return False
left, right = left + 1, right - 1
return True
时间复杂度：O(∣s∣)，其中 ∣s∣ 是字符串 s 的长度。
空间复杂度：O(1)。
第十三题、680.验证回文串2
方法一：贪心
考虑最朴素的方法：首先判断原串是否是回文串，如果是，就返回 true；如果不是，则枚举每一个位置作为被删除的位置，再判断剩下的字符串是否是回文串。这种做法的渐进时间复杂度是 O(n^2 ) 的，会超出时间限制。
换一种想法。首先考虑如果不允许删除字符，如何判断一个字符串是否是回文串。常见的做法是使用双指针。定义左右指针，初始时分别指向字符串的第一个字符和最后一个字符，每次判断左右指针指向的字符是否相同，如果不相同，则不是回文串；如果相同，则将左右指针都往中间移动一位，直到左右指针相遇，则字符串是回文串。
在允许最多删除一个字符的情况下，同样可以使用双指针，通过贪心实现。初始化两个指针 low 和 high 分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同，如果相同，则更新指针，将 low 加 1，high 减 1，然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时就分成两种情况：即删除左指针对应的字符，留下子串 s[low+1:high]，或者删除右指针对应的字符，留下子串 s[low:high−1]。当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后就以成为回文串。
class Solution:
def validPalindrome(self, s: str) -> bool:
# 定义一个辅助函数，用于检查给定范围内的子字符串是否是回文
def checkPalindrome(low, high):
i, j = low, high # 初始化两个指针，分别指向子字符串的开头和结尾
while i < j: # 当两个指针没有相遇时，继续循环
if s[i] != s[j]: # 如果当前指向的两个字符不相等
return False # 则子字符串不是回文，返回False
i += 1 # 否则，将左指针向右移动一位
j -= 1 # 同时将右指针向左移动一位
return True # 如果循环结束都没有返回False，则子字符串是回文，返回True
low, high = 0, len(s) - 1 # 初始化两个指针，分别指向原字符串的开头和结尾
while low < high: # 当两个指针没有相遇时，继续循环
if s[low] == s[high]: # 如果当前指向的两个字符相等
low += 1 # 则将左指针向右移动一位
high -= 1 # 同时将右指针向左移动一位
else: # 如果当前指向的两个字符不相等
# 尝试移除左指针指向的字符，检查剩余的子字符串是否是回文
# 或者尝试移除右指针指向的字符，检查剩余的子字符串是否是回文
# 如果其中至少有一种情况是回文，则原字符串可以视为有效回文
return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)
return True # 如果循环结束都没有返回False，则原字符串是回文，返回True
时间复杂度：O(n)，其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n)，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
空间复杂度：O(1)。只需要维护有限的常量空间。
第十四题、205.同构字符串
方法一：哈希表
此题是「290. 单词规律」的简化版，需要判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t 中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。
以示例 2 为例，
输入：s = "foo", t = "bar"
输出：false
t 中的字符 a 和 r 虽然有唯一的映射 o，但对于 s 中的字符 o 来说其存在两个映射 {a,r}，故不满足条件。
因此，维护两张哈希表，第一张哈希表 s2t 以 s 中字符为键，映射至 t 的字符为值，第二张哈希表 t2s 以 t 中字符为键，映射至 s 的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标 index 对应的字符 s[index] 已经存在映射且不为 t[index] 或当前下标 index 对应的字符 t[index] 已经存在映射且不为 s[index]）时说明两个字符串无法构成同构，返回 false。
如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回 true 即可。
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
# 使用字典来存储s到t的映射和t到s的映射
s2t = {}
t2s = {}
# 检查两个字符串的长度是否相等，如果不等则直接返回False
# 但在这个特定的解法中，我们假设输入的两个字符串长度总是相等的
# 如果需要，可以添加一个长度检查作为优化
# 遍历字符串s和t（它们长度相同）
for i in range(len(s)):
x = s[i]
y = t[i]
# 检查x是否已经在s2t中有映射，且映射的值不是y
# 或者y是否已经在t2s中有映射，且映射的值不是x
# 如果任一条件满足，则返回False
if (x in s2t and s2t[x] != y) or (y in t2s and t2s[y] != x):
return False
# 如果x和y都没有对应的映射，或者映射的值与当前值相同
# 则在s2t和t2s中分别添加x到y和y到x的映射
s2t[x] = y
t2s[y] = x
# 如果遍历完整个字符串都没有返回False，则说明s和t是同构的
return True
时间复杂度：O(n)，其中 n 为字符串的长度。只需同时遍历一遍字符串 s 和 t 即可。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要 O(∣Σ∣) 的空间。
