因为数组中有正有负有0，因此每次遇到一个数，要不要将其加入我们所求的连续子数组里面，是个问题，有可能加入了会更大，有可能加入了会更小，而且我们要求连续的最大值，因此这类有状态转移的问题可以考虑动态规划。
step 1：可以用
d
p
dp
dp 数组表示以下标
i
i
i 为终点的最大连续子数组和。
step 2：遍历数组，每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么这个元素本身就更大，要么会更小，更小我们就舍弃，因此状态转移为
d
p
[
i
]
=
m
a
x
(
d
p
[
i
−
1
]
+
a
r
r
a
y
[
i
]
,
a
r
r
a
y
[
i
]
)
dp[i]=max(dp[i−1]+array[i],array[i])
dp[i]=max(dp[i−1]+array[i],array[i])。
step 3：因为连续数组可能会断掉，每一段只能得到该段最大值，因此我们需要维护一个最大值。
class Solution:
def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
dp = [0] * len(array)
# 初始状态
dp[0] = array[0]
maxsum = dp[0]
for i in range(1,len(array)):
# 状态转移
dp[i] = max(dp[i-1] + array[i], array[i])
# 维护最大值
maxsum = max(maxsum,dp[i])
return maxsum
时间复杂度：
O
(
n
)
O(n)
O(n)，其中 n 为数组长度，遍历一次数组。
空间复杂度：
O
(
n
)
O(n)
O(n)，动态规划辅助数组长度为 n。
回文串，有着左右对称的特征，从首尾一起访问，遇到的元素都是相同的。但是我们这里正是要找最长的回文串，并不事先知道长度，怎么办？判断回文的过程是从首尾到中间，那我们找最长回文串可以逆着来，从中间延伸到首尾，这就是中心扩展法。
step 1：遍历字符串每个字符。
step 2：以每次遍历到的字符为中心（分奇数长度和偶数长度两种情况），不断向两边扩展。
step 3：如果两边都是相同的就是回文，不断扩大到最大长度即是以这个字符（或偶数两个）为中心的最长回文子串。
step 4：我们比较完每个字符为中心的最长回文子串，取最大值即可。
class Solution:
# 每个中心点开始拓展
def fun(self, s:str, begin:int, end:int):
while begin >= 0 and end <= len(s) and s[begin] == s[end]:
begin = begin - 1
end = end + 1
return end - begin - 1
def getLongestPalindrome(self , A: str) -> int:
maxlen = 1
# 以每个点为中心
for i in range(len(A)-1):
# 分奇数长度和偶数长度向两边拓展
maxlen = max(maxlen, max(self.fun(A,i,i), self.fun(A,i,i+1)))
return maxlen
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，其中 n 为字符串长度，遍历字符串每个字符，每个字符的扩展都要
O
(
n
)
O(n)
O(n)。
空间复杂度：
O
(
1
)
O(1)
O(1)，常数级变量，无额外辅助空间。
方法一讨论了两种情况，子串长度为奇数和偶数的情况，但其实我们可以对字符串添加不属于里面的特殊字符，来让所有的回文串都变成奇数形式。同时上述中心扩展法有很多重复计算，manacher就可以优化。
Manacher算法实际上就是对枚举对称中心这一做法的优化。
字符个数的奇偶性不同，对称中心也是不同的，例如对于奇回文串 a b a a b a aba，对称中心点为 b b b，对于偶回文串 a b b a a b b a abba，对称中心点则为 b b b b bb 中间，为了统一对称点，一般的做法是，将原字符串 s s s 的首尾以及相邻的两个字符中间插入一个不会出现的字符（例如：#）这样会统一成一个奇回文串，新字符串长度 = 原串 * 2 + 1。例如原串： a b b a a b b a abba。新字符串： ∗ a ∗ b ∗ b ∗ a ∗ ∗a∗b∗b∗a∗ ∗a∗b∗b∗a∗。
step 1：我们用
m
a
x
p
o
s
maxpos
maxpos 表示目前已知的最长回文子串的最右一位的后一位，用
i
n
d
e
x
index
index 表示当前的最长回文子串的中心点。
step 2：对于给定的
i
i
i 我们找一个和它关于
i
n
d
e
x
index
index 对称的
j
j
j ，也就是
i
n
d
e
x
−
j
=
=
i
−
i
n
d
e
x
index−j==i−index
index−j==i−index，换言之就是
j
=
=
2
∗
i
n
d
e
x
−
i
j==2∗index−i
j==2∗index−i。
step 3：
i
i
i 和
j
j
j 的最长回文子串在
i
n
d
e
x
index
index 的回文串范围内的部分应该是一模一样的，但是在外面的部分就无法保证了，当然，最好的情况是
i
i
i 和
j
j
j 的回文子串范围都很小，这样就保证了它们的回文子串一定一模一样，对于超出的部分我们也没有办法, 只能手动使用中心扩展。
step 4：最后答案计算的时候需要考虑使用预处理，长度被加了一倍，于是结果是
m
a
x
(
m
p
[
i
]
−
1
)
max(mp[i]-1)
max(mp[i]−1)。
对于 I P IP IP 字符串，如果只有数字，则相当于需要我们将 I P IP IP 地址的三个点插入字符串中，而第一个点的位置只能在第一个字符、第二个字符、第三个字符之后，而第二个点只能在第一个点后 1 − 3 1-3 1−3 个位置之内，第三个点只能在第二个点后 1 − 3 1-3 1−3 个位置之内，且要要求第三个点后的数字数量不能超过 3 3 3，因为 I P IP IP 地址每位最多 3 3 3 位数字。
step 1：依次枚举这三个点的位置。
step 2：然后截取出四段数字。
step 3：比较截取出来的数字，不能大于 255，且除了 0 以外不能有前导 0，然后才能组装成
I
P
IP
IP 地址加入答案中。
class Solution:
def restoreIpAddresses(self , s: str) -> List[str]:
res = []
n = len(s)
i = 1
# 遍历第一个点的位置，只可能在第1、2、3个数之后
while i < 4 and i < n - 2:
# 第二个点的位置，只能在第一个点的后三位之内
j = i + 1
while j < i + 4 and j < n - 1:
# 第三个点的位置，只能在第二个点的后三位之内
k = j + 1
while k < j + 4 and k < n:
# 最后一段的剩余数字不能超过3位
if n - k >= 4:
k = k + 1
continue
# 从点的位置分段截取
a = s[0:i]
b = s[i:j]
c = s[j:k]
d = s[k:]
# IP 每个数字不大于 255
if int(a) > 255 or int(b) > 255 or int(c) > 255 or int(d) > 255:
k = k + 1
continue
# 排除以 0 开头的多个字符的情况
if len(a) != 1 and a[0] == '0' or len(b) != 1 and b[0] == '0' or len(c) != 1 and c[0] == '0' or len(d) != 1 and d[0] == '0':
k = k + 1
continue
# 组装 IP 地址
temp = a + '.' + b + '.' + c + '.' + d
res.append(temp)
k = k + 1
j = j + 1
i = i + 1
return res
时间复杂度：如果将 3 看成常数，则复杂度为
O
(
1
)
O(1)
O(1)，如果将 3 看成字符串长度的 1/4，则复杂度为
O
(
n
3
)
O(n^3)
O(n3)，三次嵌套循环
空间复杂度：如果将 3 看成常数，则复杂度为
O
(
1
)
O(1)
O(1)，如果将3看成字符串长度的 1/4，则复杂度为
O
(
n
)
O(n)
O(n)，4 个记录截取字符串的临时变量。res 属于返回必要空间。
对于 IP 地址每次取出一个数字和一个点后，对于剩余的部分可以看成是一个子问题，因此可以使用递归和回溯将点插入数字中。
step 1：使用 step 记录分割出的数字个数，index 记录递归的下标，结束递归是指 step 已经为 4，且下标到达字符串末尾。
step 2：在主体递归中，每次加入一个字符当数字，最多可以加入三个数字，剩余字符串进入递归构造下一个数字。
step 3：然后要检查每次的数字是否合法（不超过 255 且没有前导 0）。
step 4：合法 IP 需要将其连接，同时递归完这一轮后需要回溯。
class Solution:
def __init__(self):
# 存储最终所有的结果
self.res = []
# 待分割的字符串
self.s = ''
# 用于拼装某一个的结果
self.nums = ''
# step 表示第几个数字， index 表示字符串下标
def dfs(self, step:int, index:int):
# 当前分割出的字符串 cur
cur = ''
# 分割出了 4 个数字，则结束一次分割
if step == 4:
# 下标需要走到末尾
if index != len(self.s):
return
self.res.append(self.nums)
else:
i = index
# 最长遍历3位
while i < index + 3 and i < len(self.s):
cur = cur + self.s[i]
# 字符串转数字
num = int(cur)
# temp 为了回溯用
temp = self.nums
# 不能超过 255 且不能有前导 0
if num <= 255 and (len(cur) == 1 or cur[0] != '0'):
# 添加点
if step != 3:
self.nums = self.nums + cur + '.'
else:
self.nums = self.nums + cur
# 递归，step 每加 1，可以理解为加一个点
self.dfs(step+1, i+1)
# 回溯
self.nums = temp
i = i + 1
def restoreIpAddresses(self , s: str) -> List[str]:
self.s = s
self.dfs(0,0)
return self.res
时间复杂度：
O
(
3
n
)
O(3^n)
O(3n)，3 个分枝的树型递归。
空间复杂度：
O
(
n
)
O(n)
O(n)，递归栈深度为 n。
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 s t r 1 str1 str1 的前 i i i 个字符和 s t r 2 str2 str2 的前 j j j 个字符的编辑距离。
(以下说的相等是指我们已经知道它们的编辑距离)
最终 d p [ i ] [ j ] dp[i][j] dp[i][j] 为上面三种状态的最小值： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1
我们还要考虑边界情况，当
s
t
r
1
str1
str1 为空时，编辑距离就为
s
t
r
2
str2
str2 的长度（
s
t
r
1
str1
str1 依次插入
s
t
r
2
str2
str2 个字符），当
s
t
r
2
str2
str2 为空时编辑距离就为
s
t
r
1
str1
str1 的长度（
s
t
r
1
str1
str1 依次删除每个字符）。
class Solution:
def editDistance(self , str1: str, str2: str) -> int:
len1 = len(str1)
len2 = len(str2)
if len1 == 0 or len2 == 0:
return len1 + len2
dp = [[0] * (len2+1) for i in range(len1+1)]
# 初始化边界
for i in range(1,len1+1):
dp[i][0] = dp[i-1][0] + 1
for i in range(1,len2+1):
dp[0][i] = dp[0][i-1] + 1
# 遍历第一个字符串的每个位置
for i in range(1,len1+1):
# 遍历第二个字符串的每个位置
for j in range(1,len2+1):
# 若是字符相同，此处不用编辑
if str1[i-1] == str2[j-1]:
# 直接等于二者前一个的距离
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
return dp[len1][len2]
时间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中
m
、
n
m、n
m、n 分别为两个字符串的长度，初始化
d
p
dp
dp 数组单独遍历两个字符串，后续动态规划过程两层遍历。
空间复杂度：
O
(
m
n
)
O(mn)
O(mn)，辅助数组
d
p
dp
dp 的空间。
如果是只有小写字母，那么直接比较字符是否相同即可匹配，如果再多一个’.‘，可以用它匹配任意字符，只要对应str中的元素不为空就行了。但是多了’*'字符，它的情况有多种，涉及状态转移，因此我们用动态规划。
step 1：设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 s t r str str 前 i i i 个字符和 p a t t e r n pattern pattern 前 j j j 个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）
step 2： （初始条件） 首先，毋庸置疑，两个空串是直接匹配，因此 d p [ 0 ] [ 0 ] = t r u e dp[0][0]=true dp[0][0]=true。然后我们假设 s t r str str 字符串为空，那么 p a t t e r n pattern pattern 要怎么才能匹配空串呢？答案是利用 * 字符出现 0 次的特性。遍历 p a t t e r n pattern pattern 字符串，如果遇到 * 意味着它前面的字符可以出现 0 次，要想匹配空串也只能出现 0，那就相当于考虑再前一个字符是否能匹配，因此 d p [ 0 ] [ i ] = d p [ 0 ] [ i − 2 ] dp[0][i]=dp[0][i−2] dp[0][i]=dp[0][i−2]。
step 3： （状态转移） 然后分别遍历 s t r str str 与 p a t t e r n pattern pattern 的每个长度，开始寻找状态转移。
class Solution:
def match(self , str: str, pattern: str) -> bool:
n1 = len(str)
n2 = len(pattern)
# dp[i][j] 表示 str 前 i 个字符和 pattern 前 j 个字符是否匹配
dp = [[False] * (n2+1) for i in range(n1+1)]
# 两个都为空串，自然匹配
dp[0][0] = True
# 初始化 str 为空的情况
for i in range(2, n2+1):
if pattern[i-1] == '*':
# 与再前一个能否匹配空串有关
dp[0][i] = dp[0][i-2]
# 遍历 str 每个长度
for i in range(1, n1+1):
for j in range(n2+1):
# 当前字符不为 *，用 . 去匹配或字符直接相同
if pattern[j-1] != '*' and (pattern[j-1] == '.' or pattern[j-1] == str[i-1]):
dp[i][j] = dp[i-1][j-1]
# 当前字符为 *
elif j >= 2 and pattern[j-1] == '*':
# 若是前一位为 . 或者前一位可以直接匹配
if pattern[j-2] == '.' or pattern[j-2] == str[i-1]:
# 转移情况
dp[i][j] = dp[i-1][j] or dp[i][j-2]
else:
# 不匹配
dp[i][j] = dp[i][j-2]
return dp[n1][n2]
时间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中 m 和 n 分别为字符串和模版串的长度，初始化遍历矩阵一边，状态转移遍历整个
d
p
dp
dp 矩阵。
空间复杂度：
O
(
m
n
)
O(mn)
O(mn)，动态规划辅助数组
d
p
dp
dp 的空间。
该方法是为了快速通过机试，面试不推荐。
import re
class Solution:
def match(self , str: str, pattern: str) -> bool:
# 匹配字符串的开始 ^
# 匹配字符串的结束 $
if re.match('^' + pattern + '$', str):
return True
else:
return False
因为括号需要一一匹配，而且先来的左括号，只能匹配后面的右括号，因此可以考虑使用栈的先进后出功能，使括号匹配。
step 1：可以使用栈来记录左括号下标。
step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
step 3：然后长度则更新为当前下标与栈顶下标的距离。
step 4：遇到不符合的括号，可能会使栈为空，因此需要使用 start 记录上一次结束的位置，这样用当前下标减去 start 即可获取长度，即得到子串。
step 5：循环中最后维护子串长度最大值。
class Solution:
def longestValidParentheses(self , s: str) -> int:
res = 0
# 记录上一次连续括号结束的位置
start = -1
a = []
for i in range(len(s)):
# 遇到左括号，则将其下标入栈
if s[i] == '(':
a.append(i)
# 遇到右括号
else:
# 如果此时栈为空，则是不合法状态，设置结束位置
if len(a) == 0:
start = i
else:
# 弹出左括号
a.pop()
# 栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
if len(a) != 0:
res = max(res, i-a[-1])
# 栈中没有括号，说明左右括号匹配完，减去上一次结束的位置就是长度
else:
res = max(res, i-start)
return res
另一种写法。
class Solution:
def longestValidParentheses(self , s: str) -> int:
res = 0
a = []
a.append(-1)
for i in range(len(s)):
# 遇到左括号，则将其下标入栈
if s[i] == '(':
a.append(i)
# 遇到右括号
else:
a.pop()
# 记录最后一个没有被匹配的右括号的下标
if len(a) == 0:
a.append(i)
else:
res = max(res, i-a[-1])
return res
时间复杂度：
O
(
n
)
O(n)
O(n)，其中n为字符串长度，遍历整个字符串。
空间复杂度：
O
(
n
)
O(n)
O(n)，最坏全是左括号，栈的大小为 n。
step 1：用 d p [ i ] dp[i] dp[i] 表示 以下标为 i i i 的字符为结束点的最长合法括号长度。
step 2：很明显知道左括号不能做结尾，因此左括号都是 d p [ i ] = 0 dp[i]=0 dp[i]=0。
step 3：我们遍历字符串，因为第一位不管是左括号还是右括号 d p dp dp 数组都是 0，因此跳过，后续只查看右括号的情况，右括号有两种情况：
step 4：每次检查完维护最大值即可。
class Solution:
def longestValidParentheses(self , s: str) -> int:
if len(s) == 0:
return 0
# dp[i] 表示以下标为 i 的字符为结束点的最长合法括号长度
dp = [0 for i in range(len(s))]
# 第一位不管是左括号还是右括号都是 0，可以忽略
for i in range(1,len(s)):
# 左括号都为 0，右括号才合法
if s[i] == ')':
# 该右括号的前一位就是左括号
if s[i-1] == '(':
if i >= 2:
dp[i] = dp[i-2] + 2
else:
dp[i] = 2
# 找到这一段连续合法括号序列前第一个左括号做匹配
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
if i - dp[i-1] > 1:
dp[i] = dp[i - dp[i-1] - 2] + dp[i-1] + 2
else:
dp[i] = dp[i-1] + 2
return max(dp)
时间复杂度：
O
(
n
)
O(n)
O(n)，其中 n 为字符串长度，遍历一次字符串。
空间复杂度：
O
(
n
)
O(n)
O(n)，动态规划辅助数组的长度为 n。