输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
思路：回溯算法（N叉树）
# @lc code=start
class Solution:
def isMatch(self,s: str, p: str) -> bool:
if s=="" and p=="":
return True
if p=="":
return False
len1=len(s)
n1=0
m1=""
len2=len(p)
for i in range(1,len2):
if p[i]=="*" and p[i-1]=="*":
continue
else :
m1=m1+p[i-1]
n1=1+n1
p=m1+p[-1]
len2=len(p)
def submacth(i,j):
if i==len1 and j==len2:
return True
if j==len2:
return False
if i==len1 and (p[j:]!="*"*len(p[j:])):
#print(False)
return False
if p[j]!="*" :
if p[j]=="?"or p[j]==s[i]:
i=i+1
j=j+1
return submacth(i,j)
else:
#print(False)
return False
if p[j]=="*" and j==len2-1:
#print("3333")
l=len1
h=len2
return submacth(l,h)
if p[j]=="*" and j<len2-1:
for m in range(i,len1):
if s[m]==p[j+1] or p[j+1]=="?":
#print(m,j+1,"hh")
l=m+1
h=j+2
if submacth(l,h):
return True
return False
return submacth(0,0)
需改进：
动态规划步骤：
确定dp[i][j]状态含义
确定 状态转移方程
确定dp初始值
参考官方题解：动态规划问题dp[i][j]表示s的前i个字符和 p的前j个字符是否匹配。在进行状态转移时，我们可以考虑模式 p 的第 j 个字符 pj，与之对应的是字符串 s 中的第 i 个字符si：
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, n + 1):
if p[i - 1] == '*':
dp[0][i] = True
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
max_len = 1
begin = 0
# dp[i][j] 表示 s[i..j] 是否是回文串
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 递推开始
# 先枚举子串长度
for L in range(2, n + 1):
# 枚举左边界，左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
j = L + i - 1
# 如果右边界越界，就可以退出当前循环
if j >= n:
break
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3:
dp[i][j] = True
else:
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]
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
这份模板很重要，后面做回溯法的题目都靠它了！
实例： 解数独 （回溯法）
#回溯法
"""
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。
"""
# @lc code=start
class Solution:
def solveSudoku(self, board)->None:
"""
Do not return anything, modify board in-place instead.
"""
#判断改行、列、3*3小格子是否满足数独规则：
def isRowSafe(row,value):
for i in range(9):
if board[row][i]==value:
return False
return True
def isColSafe(col,value):
for i in range(9):
if board[i][col]==value:
return False
return True
def isSmallboxSafe(row,col,value):
inirow=row//3*3
inicol=col//3*3
for i in range(3):
for j in range(3):
if board[i+inirow][j+inicol]==value:
return False
return True
#判断该位置是否可行
def isSafe(row,col,value):
return isRowSafe(row,value) and isColSafe(col,value) and isSmallboxSafe(row,col,value)
#解数独，结束条件（回溯法，递归调用）
def solve(row,col):
if row==8 and col ==9:
return True
if col ==9:
col=0
row+=1
if board[row][col]!=".":
return solve(row,col+1)
for i in range(1,10):
if isSafe(row,col,str(i)):
i=str(i)
board[row][col] = i
if solve(row, col+1):
return board
board[row][col]="."
return False
solve(0,0)
print(board)
# @lc app=leetcode.cn id=39 lang=python3
#
# [39] 组合总和
#
# @lc code=start
class Solution:
def combinationSum(self,candidates, target: int):
nums=list()
nums.append(-1)
length=len(candidates)
rev=[target-i for i in candidates]
nums.extend([target-i for i in candidates])
while [i for i in rev if i>=min(candidates)]!=[]:
mid=list()
for i in rev:
if i<=0:
mid.extend([-1]*length)
nums.extend([-1]*length)
continue
else:
mid.extend([i-j for j in candidates])
nums.extend([i-j for j in candidates])
rev=mid
result=list()
mids=list()
for i in range(1,len(nums)):
if nums[i]!=0:
continue
else:
j=i
while 1:
if j<=length:
mids.append(candidates[j-1])
mids.sort()
print(mids)
if mids not in result :
result.append(mids)
break
elif j//length==j/length:
j=int((j-length)/length)
mids.append(candidates[-1])
else:
mids.append(candidates[j-(j//length)*length-1])
j=int(j//length)
mids=[]
return result
# @lc code=end
显示超时了…..
其实大致反方向对的，但是有些地方不太正确
尝试用回溯的方法（递归调用）
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
def firstMissingPositive(nums):
lens=len(nums)
for i in range(lens):
if nums[i]<0:
nums[i]=lens+1
for i in range(lens):
num = abs(nums[i])
if num <= lens:
nums[num - 1] = -abs(nums[num - 1])
print(nums)
for i in range(lens):
if nums[i]>=0:
return i+1
return lens+1
# [37] 解数独
#
#回溯法
"""
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。
"""
# @lc code=start
class Solution:
def solveSudoku(self, board)->None:
"""
Do not return anything, modify board in-place instead.
"""
#判断改行、列、3*3小格子是否满足数独规则：
def isRowSafe(row,value):
for i in range(9):
if board[row][i]==value:
return False
return True
def isColSafe(col,value):
for i in range(9):
if board[i][col]==value:
return False
return True
def isSmallboxSafe(row,col,value):
inirow=row//3*3
inicol=col//3*3
for i in range(3):
for j in range(3):
if board[i+inirow][j+inicol]==value:
return False
return True
#判断该位置是否可行
def isSafe(row,col,value):
return isRowSafe(row,value) and isColSafe(col,value) and isSmallboxSafe(row,col,value)
#解数独，结束条件
def solve(row,col):
if row==8 and col ==9:
return True
if col ==9:
col=0
row+=1
if board[row][col]!=".":
return solve(row,col+1)
for i in range(1,10):
if isSafe(row,col,str(i)):
i=str(i)
board[row][col] = i
if solve(row, col+1):
return board
#回溯到上一个状态（也就是前一个solve）
board[row][col]="."
return False
solve(0,0)
print(board)
