Leetcode【60、79、93、131、842】
问题描述：【Math】60. Permutation Sequence
解题思路：
这道题是一个从 1 到 n 的数组，共有 n! 个全排列序列，找到第 k 个全排列序列。
刚开始没仔细读题就之间 DFS 回溯，很快写好但超时了哈哈哈。再读一下题目，发现如果 k 很大，要一个个找过去，所以会很慢。
实际上，这是一道数学题（找规律）。以 n = 5 举例，共有 5！= 120 个排列，我们发现：当 k <= 24，排列全部以 1 开头；24 < k <= 48，排列全部以 2 开头，以此类推。因此，我们可以一位一位的构造答案，根据 k 值判断其落在哪个区间，找到开头数字加入结果；然后，从数组中删除该开头数字，并确定 k 值位于当前区间的第几个，更新 k 值；按照上述方法进行操作，直到得到一个全排列，就是最后的答案。
以 n = 5，k = 31 为例（nums = [1,2,3,4,5]）：
- k ∈ (4!, 2*4!]，则确定 ans = "2"，数组中删除 2（nums=[1,3,4,5]），k 更新为 k = 31 - 4! = 7 （k 位于该区间的第 7 个）；
- k ∈ (3!, 2*3!]，则确定 ans = "23"，数组中删除 3（nums=[1,4,5]），k 更新为 k = 7 - 3! = 1 （k 位于该区间的第 1 个）；
- k ∈ (0, 1*2!]，则确定 ans = "231"，数组中删除 1（nums=[4,5]），k 更新为 k = 1 - 0 = 1 （k 位于该区间的第 1 个）；
- k ∈ (0, 1*1!]，则确定 ans = "2314"，数组中删除 4（nums=[4]），k 更新为 k = 1 - 0 = 1 （k 位于该区间的第 1 个）；
- k ∈ (0, 1*0!]，则确定 ans = "23145"，数组中删除 5（nums=[]），k 更新为 k = 1 - 0 = 1 （k 位于该区间的第 1 个）；
- 得到一个全排列，最终结果 ans = "23145"
Python3 实现：
class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans = ""
nums = [(i + 1) for i in range(n)]
while len(ans) != n: # 迭代方法，逐个字符加入到结果中
nf = math.factorial(len(nums) - 1)
for i in range(len(nums)):
if k <= (i + 1) * nf: # 找到k位于哪个区间
ans += str(nums[i])
del nums[i]
k -= i * nf # k位于当前区间的第几个
break
return ans
问题描述：【DFS】79. Word Search
解题思路：
这道题是给一个 m*n 的字符矩阵 board 和一个单词 word，判断 word 是否存在字符矩阵中。
这道题很明显用 DFS 回溯法去解决。做法如下：
- 在主函数中，遍历字符矩阵的每个坐标 (i, j)，如果发现
board[i][j] == word[0]，则将 board[i][j] 位置先改为 ""（因为每个位置字符只能使用一次），然后进入回溯函数search(i, j, path, wind)（path 记录单词路径，wind 为 word 索引）进行深搜判断。如果没有在 search() 函数中找到，说明没有以当前字符 board[i][j] 开头的单词，要恢复原来该位置的字符。 - 在回溯函数中，对于每个字符的上下左右四个位置进行深搜（要保证不越界），如果 board 的下一个位置的字符匹配 word 的下一个字符，则修改 board 中当前字符为 "" 进行递归调用。递归调用结束后，要先恢复原来该位置的字符，再去判断返回值是 True 还是 False。如果找到（返回值为 True，则返回 True），否则继续查找下一个位置。
Python3 实现：
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def search(i, j, path, wind): # (i,j)是匹配word第一个字符的坐标，path记录结果，wind为word索引
isfind = False
if path == word: # 找到了该单词
return True
for p in pos:
if 0 <= i+p[0] < m and 0 <= j+p[1] < n and board[i+p[0]][j+p[1]] == word[wind]:
tmp = board[i+p[0]][j+p[1]]
board[i+p[0]][j+p[1]] = ""
isfind = search(i+p[0], j+p[1], path+word[wind], wind+1)
board[i+p[0]][j+p[1]] = tmp # 先恢复原来的字符
if isfind == True: # 再判断返回结果，如果是True直接返回；如果是False继续查找
return True
return False
if len(word) == 0 or len(board) == 0:
return False
pos = [[-1,0], [1,0], [0,-1], [0,1]] # 上下左右四个位置
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
tmp = board[i][j]
board[i][j] = ""
if search(i, j, word[0], 1):
return True
board[i][j] = tmp # 如果没有找到，恢复原来的字符
return False
问题描述：【DFS】93. Restore IP Addresses
解题思路：
这道题是给一个数字字符串，返回所有可能的 IP 地址组合。
这道题和下面的 Leetcode 131 以及 Leetcode 842 做法是类似的，也是使用回溯法 DFS 对字符串前缀进行划分。注意该深搜函数 search(s, path)（s 为后半部分字符串，path 为划分的 IP 子段）的几个出口：
- 如果 len(path) > 4，不符合 IP 地址，提前终止，返回；
- 如果 s 为空串，但是 len(path) < 3，说明划分结束，但是不符合 IP 地址，也返回；
- 如果 s 为空串，且 len(path) == 4，说明找到一组解，就加入到结果列表 ans 中。
在 for 循环中，还要注意去除前导 0 以及字符串前缀数字 > 255 的情况，才能进行递归调用深搜。
Python3 实现：
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def search(s, path):
if len(path) > 4: # 不满足题意
return
if not s and len(path) < 4: # 不满足题意
return
if not s and len(path) == 4: # 找到一组解
ans.append('.'.join(path))
return
for i in range(1, len(s) + 1):
pre = s[:i] # 划分前缀
if (len(pre) > 1 and pre[0] == '0') or int(pre) > 255: # 不满足题意
continue
search(s[i:], path + [pre])
ans = []
search(s, [])
return ans
问题描述：【Brute Force、DFS】131. Palindrome Partitioning
解题思路：
这道题是给一个字符串，将字符串分割成一些子串，使得所有子串都是回文串，求所有划分的方案数。
一个子串是否是回文串可以使用 s == s[::-1] 来判断。
方法1（Brute Force）：
首先想到一种暴力解法，就是对于字符串的每个字符 s[i]，依次将 s[i] 加入到回文串前缀列表中每个回文串前缀的后面，然后再判断 s[i] 的加入能否形成新的回文串前缀。如果可以，拓展回文串前缀列表。最后，遍历完所有字符后，列表中存储的就是最终结果。
以 s = "abba" 举例：
- s[0] = a，a 本身是回文串，加入到结果列表 ans = [[a]]；
- s[1] = b，b 加入回文串前缀的后面，得到 ans = [[a,b]]；
- s[2] = b，b 先加入回文串前缀的后面，得到 ans = [[a,b,b]]；然后发现，b 的加入可以形成新的回文串 "bb"（从最后一个 b 开始往前形成子串 bb），因此拓展结果列表得到 ans = [[a,b,b], [a,bb]]；
- s[3] = a，a 先加入回文串前缀的后面，得到 ans = [[a,b,b,a], [a,bb,a]]；然后发现，a 的加入可以形成新的回文串 "abba"（注意到 ans 中两个都可以构成 "abba"，所以还要判断新加入的回文串是否之前已经加入过），因此拓展结果列表得到 ans = [[a,b,b,a], [a,bb,a], [abba]]。
这种做法时间复杂度为 O(n^4)，空间复杂度为 O(n^2)，能够 AC。
Python3 实现：
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = [[]]
for i in range(len(s)):
for a in ans: # 将当前字符加入到每个字符串前缀列表的后面
a.append(s[i])
for a in ans:
N = len(a)
st = a[-1]
for j in range(N-2, -1, -1):
st = a[j] + st # 从最后一个字符开始构造新的子串
if st == st[::-1] and a[:j] + [st] not in ans: # 判断新的子串是否是回文串，且构成的回文串前缀是否之前出现过
ans.append(a[:j] + [st]) # 将新的回文串前缀加入到结果列表中
return ans
方法2（DFS）：
其实这道题一看是求所有结果，很明显用 DFS 回溯法求解，但是刚开始没有思路，找不到如果求解的方法，最后看了别人的做法才明白。
使用回溯法的解题思路是对于字符串 s 的前缀进行划分，然后判断前缀是否是回文子串。如果是，形成临时结果，将 s 的后半部分和临时结果传入到下一层（深搜）；如果不是，那就继续划分下一个前缀。最后，传入的 s 会变成空串，这时形成的结果必定是回文串的一个划分，加入到结果列表中即可。
以 s = "aab" 举例，用 path 记录一种划分结果：
- 1、划分 s = "aab" 前缀 a，a 是回文串，将其加入 path = [a]，并且同 s = "ab" 传入到下一层；
- 2、划分 s = "ab" 前缀 a，a 是回文串，将其加入 path = [a,a]，并且同 s = "b" 传入到下一层；
- 3、划分 s = "b" 前缀 b，b 是回文串，将其加入 path = [a,a,b]，并且同 s = "" 传入到下一层；
- 4、因为 s = ""，说明划分完毕，将结果 path = [a,a,b] 加入到 ans 中，直接返回到步骤 3（没有前缀，继续返回）、步骤 2；
- 5、在步骤 2 中，划分 s = "ab" 前缀 ab，ab 不是回文串，继续划分下一个前缀；没有前缀，返回步骤 1；
- 6、在步骤 1 中，划分 s = "aab" 前缀 aa，aa 是回文串，将其加入 path = [aa]，并且同 s = "b" 传入到下一层；
- 7、划分 s = "b" 前缀 b，b 是回文串，将其加入 path = [aa,b]，并且同 s = "" 传入到下一层；
- 8、因为 s = ""，说明划分完毕，将结果 path = [aa,b] 加入到 ans 中，直接返回到步骤 7（没有前缀，继续返回）、步骤 6；
- 9、在步骤 6 中，划分 s = "aab" 前缀 aab，aab 不是回文串，继续划分下一个前缀；没有前缀，结束。
- 10、最终得到结果 ans = [[a,a,b], [aa,b]]。
优化：可以通过用区间 DP 来计算任意 s[i:j] 之间是否是回文串 【区间DP、双指针】647. Palindromic Substrings，并保存结果；然后再执行DFS，如果发现某条子串不是回文，就可以直接退出，从而减少计算量。
Python3 实现：
class Solution:
def partition(self, s: str) -> List[List[str]]:
def search(s, path):
if not s: # s 变为空串，将形成的一种结果path加入到ans中
ans.append(path[:])
for i in range(1, len(s) + 1):
pre = s[:i] # 对于s的每一个前缀
if pre == pre[::-1]: # 如果前缀是回文串，则深搜
search(s[i:], path + [pre]) # 将后半部分和临时结果传入到下一层
ans = []
search(s, [])
return ans
问题描述：【DFS】842. Split Array into Fibonacci Sequence
解题思路：
这道题是给一个数字字符串 S，将其划分成斐波那契序列。
很容易想到用 DFS 回溯法去找斐波那契序列的一种划分。类似于上面的 Leetcode 131，对于数字字符串 S 的前缀进行划分，如果 S 的前缀合法（没有前导 0 并且数字没有越界），就将 S 的后半部分和临时结果 path 传入，进行递归调用。
递归出口：
- 如果临时结果 path 长度大于等于 3，但是不满足 f[i-2] + f[i-1] = f[i]，返回 False；
- 如果临时结果 path 长度大于等于 3，且 S 为空串，说明划分完毕，保存结果
ans.extend(path)，返回 True。
第一次提交时，WA 了，报错如下：
检查了一下发现没什么问题啊？然后重新读题，很敏感的发现斐波那契序列数值要求为 <= 2 ** 31 - 1（2147483647），然后发现报错结果的最后一项 11336528511 > 2 ** 31 - 1，因此在代码中加入了数值范围的判断，就 AC 了。
Python3 实现：
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
def search(S, path):
if len(path) >= 3 and path[-3] + path[-2] != path[-1]: # 不满足斐波那契条件
return False
if not S and len(path) >= 3: # S为空串，说明可以划分
ans.extend(path) # 找到一种划分，保存结果到ans中，返回
return True
for i in range(1, len(S) + 1):
pre = S[:i] # 划分前缀
if (len(pre) > 1 and pre[0] == '0') or (int(pre) > 2 ** 31 - 1): # 不满足题意
continue
if search(S[i:], path + [int(pre)]): # 将S后半部分和临时结果传入进行递归调用
return True
return False # S本身长度小于3
ans = []
search(S, [])
return ans
