常见使用方法：
- 不同于数组，由于字符串本身是格式固定的，在python中每一次字符串合并的复杂度都是O(n)，所以遇到要修改字符串元素的问题，可以先将字符串转化为列表，增删过后再通过join函数将列表转回字符串。
- 复杂度分析：
- 时间复杂度：划分区间时的时间复杂度为 O(n/k)，每次反转复杂度是O(k)，最终时间复杂度为O(n)
- 空间复杂度：创建的新字符串的长度取决于输入字符串的长度，所以O(n)
class Solution:
def reverseStr(self, s: str, k: int) -> str:
p = 0
res = ''
while p < len(s):
if 2*k >= len(s[p: 2*k+p]) >= k:
# 剩余长度小于等于2k，大于等于k
res += self.reverse(s[p: 2*k+p], k)
else:
# 剩余长度小于k
res += self.reverse(s[p: 2*k+p], len(s[p: 2*k+p]))
p += 2*k
return res
def reverse(self, sub, k):
start = 0
end = k - 1
l = list(sub)
while start < end:
tmp = l[end]
l[end] = l[start]
l[start] = tmp
start += 1
end -= 1
return ''.join(l)- 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def replaceSpace(self, s: str) -> str:
# 如果直接使用字符串进行添加，时间复杂度比较高
# 可行的办法是将其转化为列表，添加完成后，再拼接到一起
# 时间复杂度和空间复杂度都是 O(n)
res = []
for c in s:
if c == ' ': res.append("%20")
else: res.append(c)
return "".join(res)- 状态方程
$P(i, j) = P(i+1,j−1)∧(S_i == S_j)$ - 时间复杂度：
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2: return s
max_len = 1
begin = 0
# base case
# 创建一个二维数组，并全部初始化为False
dp = [[False] * n for _ in range(n)]
# 二维数组构建好后，后面需要做的事情就是填满这个二维数组
# 表示i，j都是自己，也就是一个字符时，一定是回文字符串
for i in range(n):
dp[i][i] = True
# 枚举子串长度，开始递推，因为回文串的长度为 j - i + 1 = L
for L in range(2, n + 1): # 这样保证L能取到n
# 枚举左边界，左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界
j = L + i - 1
# 如果右边界越界，就可以退出当前循环
if j >= n:
break
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3: # 子串长度为2时
dp[i][j] = True
else: # 子串长度大于2时，由前一个值决定
dp[i][j] = dp[i + 1][j - 1]
# 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]- 复杂度分析：
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
class Solution:
def expandAroundCenter(self, s, left, right):
# 围绕中心进行扩展
# left 和 right 都从0开始
while left >= 0 and right < len(s) and s[left] == s[right]:
# 从中心向两边进行扩展，知道两边数不相等，或者超出s边界
left -= 1
right += 1
return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0
for i in range(len(s)):
# 同一位置作为中心，最终回文子串长度为奇数
left1, right1 = self.expandAroundCenter(s, i, i)
# 相邻两个位置作为中心，最终回文子串为偶数
left2, right2 = self.expandAroundCenter(s, i, i + 1)
# 谁的长度大，就采用谁的边界
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start: end + 1]- 复杂度分析：
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
- 空间复杂度：O(1)，使用常数空间
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0: return ''
if len(strs) == 1: return strs[0]
max_str = strs[0]
n = len(strs)
for i in range(1, n):
p = self.lcp(max_str, strs[i])
max_str = strs[i][:p]
if not max_str:
break
return max_str
def lcp(self, str1, str2):
# 输入两个字符串的最小长度
min_len = min(len(str1), len(str2))
p = 0 # 当作两个字符串之间的公共前缀的长度
while p < min_len and str1[p] == str2[p]:
p += 1
return p- 复杂度和上述相同
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] # 依次取第一个字符串的所有元素
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
# 当数字中遍历元素的index已经等于已知所有字符串中长度最小的那个，
# 或者有数组的对应位置不等于这个位置已知的公共字符串，程序退出
return strs[0][:i]
return strs[0]-
两个指针分别从尾至头进行遍历，分别记录每次相加时的和，是否进位，个位是多少，也就是模拟计算过程
-
如果一个字符串有遍历完了，就令这个字符串这个位置的值为0，等待另一个字符串遍历完
-
难点：别忘记最后要加上一个进位值
-
复杂度分析：
- 时间复杂度： O(max(M,N))，其中 M，N 为两字符串长度，按位遍历一遍数字（以较长的数字为准）
- 空间复杂度：O(1)，常数空间
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
# 两个指针分别指向两个字符串的尾部，从尾向头进行遍历
p1 = len(num1)-1
p2 = len(num2)-1
res = ''
carry = 0
while p1 >= 0 or p2 >= 0:
# 两个指针都小于零时，当前加数设定为0，知道两个字符串否遍历完
n1 = int(num1[p1]) if p1 >= 0 else 0 # 获得当前数
n2 = int(num2[p2]) if p2 >= 0 else 0
tmp = n1 + n2 + carry # 当前数求和+上一个进位
carry = tmp // 10 # 判断是否进位
res = str(tmp - carry * 10) + res # 字符串相加
p1 -= 1
p2 -= 1
return str(1) + res if carry else res # 将最后一个carry加上- 左右括号都有大于0个括号可以使用时，才会产生新的分支
- 产生左分支时，需要保证左括号还有剩余
- 产生右括号时，需要保证剩余的左括号数量要大于剩余的右括号数量，否则不能添加
- 当剩余的左右括号都为0时，就可以向列表中添加这个字符串了
- 复杂度分析：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
cur_str = ''
def dfs(cur_str, left, right):
"""
:param cur_str: 从根结点到叶子结点的路径字符串
:param left: 左括号还可以使用的个数
:param right: 右括号还可以使用的个数
:return:
"""
if left == 0 and right == 0:
res.append(cur_str)
return
if right < left:
return
if left > 0:
dfs(cur_str + '(', left - 1, right)
if right > 0:
dfs(cur_str + ')', left, right - 1)
dfs(cur_str, n, n)
return res- 复杂度分析：
- 时间复杂度：
O(N) - 空间复杂度：
O(N)
- 时间复杂度：
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2: return s
res = ['' for _ in range(numRows)]
i = 0
flag = -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1:
flag = -flag
i += flag
return "".join(res)- 复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
- 时间复杂度：
class Solution:
def romanToInt(self, s: str) -> int:
d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50,
'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
# d 中记录的是所有罗马数字的组合及对应的数值
# 如果罗马数字是两位，则这里的数值为真实值-前一个数值的值
Sum = 0
for i, n in enumerate(s):
# cur 表示当前的子串，max函数为了方式出现(-1, 0)的情况
# 也就是说，i=0时处理的子串是一个字符，之后处理的都是两个字符
cur = s[max(i-1, 0): i+1]
# 使用python的字典的get方法，找到返回对应值，没找到则返回默认值
val = d.get(cur, d[n])
Sum += val
return Sum| ' ' | +/- | Number | Other | |
|---|---|---|---|---|
| start | start | signed | in_number | end |
| signed | end | end | in_number | end |
| in_number | end | end | in_number | end |
| end | end | end | end | end |
-
说明：表中的行表示不同状态，列表示输入的字符，一个状态
$s$ 在输入字符$c$ 的条件下，变为另一个状态$s^‘$ ；比如，如果当前的状态为start，如果输入的字符是+/-，那么这个状态就会变为signed。 -
将上表这个结果添加到代码中
-
注意：
- 对于number状态，需要计算这个值，并判断是否在两个边界内
- 对于signed状态，等所有结果都计算完毕后，再添加符号
-
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
INT_MAX = 2 ** 31 - 1 # 设定最大值和最小值的范围
INT_MIN = -2 ** 31
class Automaton:
def __init__(self):
self.state = 'start' # 指定初始状态
self.sign = 1 # 设定初始符号
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):
# 通过输入的字符来确定table中状态的索引
if c.isspace():
return 0
if c == '+' or c == '-':
return 1
if c.isdigit():
return 2
return 3
def get(self, c):
self.state = self.table[self.state][self.get_col(c)]
if self.state == 'in_number':
# 如果状态为number，则计算这个值
# 前面的数乘10，个位数为新的字符数
self.ans = self.ans * 10 + int(c)
self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
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)
- 空间复杂度：O(n)，使用栈空间，最多把所有元素全部入栈
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 使用一个栈空间来记录有效括号的下标
# 只有栈为空时，')'才能够入栈，这样就将单独存在的')'加入到栈里，不参与长度计算中
if not s: return 0
stack = []
ans = 0
for i in range(len(s)):
if not stack or s[i] == '(' or s[stack[-1]] == ')':
stack.append(i)
else:
stack.pop()
# 计算长度时，取当前元素下标与出栈一个元素后栈顶元素下表的差，与上一个长度的最大值
ans = max(ans, i - (stack[-1] if stack else -1))
return ans- 复杂度：
- 时间复杂度：O(mn)
- 空间复杂度：O(1)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# 两个指针分别从两个字符串的末尾开始遍历
p1, p2 = len(num1)-1, len(num2)-1
res = 0
car2 = str(1)
while p2 >= 0:
car1 = str(1) # 进位的结果
# 两个位置乘积的结果
while p1 >= 0:
ans = int(num1[p1]) * int(num2[p2]) * int(car1) * int(car2)
res += ans
p1 -= 1
car1 += '0'
p1 = len(num1)-1
p2 -= 1
car2 += '0'
return str(res)class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = [] # 存放最终结果
n = len(s) # 输入字符串长度
def backtrack(i, tmp, flag):
"""
i: IP中第几个数字段正在问配
tmp：表示为一种分法
flag：还有几个数字段待分配
"""
# 字符s遍历完，且没有剩余的数字段共匹配了，就将结果添加，然后停止回溯
if i == n and flag == 0:
res.append(tmp[:-1])
return
# 没有剩余的数字段时，结束回溯
if flag < 0:
return
for j in range(i, i + 3):
# 每3个作为一组
if j < n:
if i == j and s[j] == "0":
# 如果第一个位置就为0，那么将当前数字字段加入，也就是0
backtrack(j + 1, tmp + s[j] + ".", flag - 1)
break
if 0 < int(s[i:j + 1]) <= 255:
# s[i: j+1] 表示连续的三个数，则将连续的三个数加入tmp
backtrack(j + 1, tmp + s[i: j + 1] + ".", flag - 1)
backtrack(0, "", 4)
return res推荐使用第二种方法
-
拿到一个字符串s时，首先尝试在每两个字符位置插入一个
.来生成一种组合，如果这个组合不满足有效性，则去掉最后一个添加的.再进行判断， -
其主要难点在于如何判断当前IP组合是有效的，有效性的判断分为三部分：
- 当 当前索引值超过整个已拼接字符串的长度时，IP无效
- 当 当前IP段的起始字符为0且IP段长度大于1时，IP无效
- 当 当前IP段的数字值大于255时，IP无效
- 只要在以上三种情况之外的所有情况，都是有效的
-
复杂度分析（SEG_COUNT=4 表示IP地址的段数）：
- 时间复杂度：$O(3^\text{SEG_COUNT} \times |s|)$
- 空间复杂度：$O(SEG_COUNT)$
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def isValid(s, start, end):
"""传入字符串s，开始处理s的起始位置，字符串s末尾索引"""
if start > end:
# 如果已经超出去了，就返回无效
return False
if s[start] == '0' and start != end:
# 如果第一位是0，而且这个IP段长度大于1，返回无效
# start != end 表示这一个IP段的长度已经大于1了，此时的s是添加"."后的结果，
# end表示s末尾索引，如果start表示第4个IP段的第一个字符索引
# 如果有效，那么s[start]==0时，start = end，否则无效
return False
num = 0
for i in range(start, end + 1):
if s[i] > '9' or s[i] < '0':
# 字符如果大于9或者小于0，返回无效
return False
num = num*10 + (int(s[i]) - 0)
if num > 255:
# 转为int型后，如果超出边界，则无效
return False
# 都不满足，则返回有效
return True
def backtracking(s, startindex, pointnum):
"""
传入【字符串s，起始位置，"."的个数】
"""
if pointnum == 3:
# 在字符串中插入了3个"."时，说明已将s划分完成，此时进行有效性判断
if isValid(s, startindex, len(s)-1):
# 如果返回有效，则将结果添加到res中
res.append(s)
return # 剪枝
for i in range(startindex, len(s)):
# 此处i为s的所有索引
if isValid(s, startindex, i):
# 这里的有效性判断，主要是为了验证已划分出来的，最右边的区间是否有效
# 这里相当于添加并移动了“.”的位置在整个s中
s = s[:i+1] + '.' + s[i+1:]
pointnum += 1
backtracking(s, i+2, pointnum) # 这里+2是由于中间插入了一个"."
# 这里传入的i+2作为下一次的startindex，表示的是下一个待处理的字符
pointnum -= 1 # 不满足这个条件时，pointnum-1表示去掉上一个区间的划分
s = s[:i+1] + s[i+2:] # 去掉上一个添加的"."，接下来重新进行循环，重新分配"."的位置
else:
break
# 如果字符串长度大于12，则直接返回空
if len(s) > 12:
return [] # 剪枝
res = list()
# 其中每个IP字段中当前指向的位置在0，1，2三个数当中的一个，共有4个IP字段
backtracking(s, 0, 0)
return res214，最短回文串，困难
核心方法：KMP 算法
直观理解：找到字符串
- 长度为
$|s| - |s'|$ 的前缀$s_1$ - 长度为
$|s'|$ 的后缀$s_2$
因此，要找到最短的
-
部分匹配表（Partial Match Table）
-
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。
char a b a b a b c a index 0 1 2 3 4 5 6 7 value 0 0 1 2 3 4 0 1 -
对于“abab”来说，其前缀集合为{'a', 'ab', 'aba'}，后缀集合为{'b', 'ab', 'bab'}，两个集合的交集为{'ab'}，所以长度最长的元素长度就是2，对应表中的2
-
注意，解释中第一段的最后一句话： 具体的做法是，保持指针 i 不动，然后将 j 指针指向模式字符串的PMT[j-1]位的即可 。这里的PMT[j-1]指的就是表中PMT的值，当前j=6，那么j-1=5，在PMT中5对应着的PMT值就是4（PMT[5] = 4），所以 j 指向的值就是模式字符串中的第4位，也就是“abababc”中的第三个a。
-
next数组
-
我们看到如果是在
j位失配，那么影响j指针回溯的位置的其实是第j −1位的PMT值。所以为了编程的方便，我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。 -
其中要注意的一个技巧是，在把
PMT进行向右偏移时，第0位的值，我们将其设成了-1,这只是为了编程的方便，并没有其他的意义。 -
char a b a b a b c a index 0 1 2 3 4 5 6 7 pmt 0 0 1 2 3 4 0 1 next -1 0 0 1 2 3 4 0 -
==如何快速求得next数组？==
- 以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
- 具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。
-
-
时间复杂度：O(n)
-
空间复杂度：O(n)
class Solution:
def shortestPalindrome(self, s: str) -> str:
def get_table(p):
# 构建pmt数组
table = [0] * len(p)
i = 1 # i从1开始
j = 0 # j从0开始
while i < len(p):
if p[i] == p[j]:
# 如果两个位置能够匹配，那么i和j同时右移，
j += 1
table[i] = j # 更新i位置的pmt，如果前面能够匹配上，后面就是前面pmt+1
i += 1
else:
# 如果不能匹配，那么需要判断j是否在字符串的第0位
if j > 0:
# 如果不在第0位，则j的取值为该位置对应的next数
# 已经匹配的位置不再比较，将j指针指向模式字符串的table[j −1]位即可
j = table[j - 1]
else:
# 如果j还在第0位，则将i向右移动一位，j保持模式字符串的首位
i += 1
j = 0
return table
# 将s翻转，然后通过#与原来的s进行拼接，通过新的字符串构建pmt数组
table = get_table(s + "#" + s[::-1])
# table[-1]表示的是前缀集合和后缀集合的交集中最长字符串的长度，
# 这个位置后面的就是要翻转后添加到s前面的字符
return s[table[-1]:][::-1] + s461，汉明距离，简单
核心方法：二进制异或
计算两个数的异或结果，然后求解结果中1的个数
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')核心方法：转化为二进制字符串然后按位比较
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
bx, by = bin(x)[2:].zfill(32), bin(y)[2:].zfill(32)
count = 0
for i in range(32):
if bx[i] != by[i]:
count += 1
return count