经典题目（7）正则表达式匹配；三数之和

BM76 正则表达式匹配请实现一个函数用来匹配包括.和*的正则表达式。1.模式中的字符.表示任意一个字符2.模式中的字符*表示它前面的字符可以出现任意次包含0次。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串aaa与模式a.a和ab*ac*a匹配但是与aa.a和ab*a均不匹配数据范围:1.str 只包含从 a-z 的小写字母。2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *无连续的 *。3. 0≤str.length≤264. 0≤pattern.length≤26class Solution: def match(self , str: str, pattern: str) - bool: # write code here m,nlen(str),len(pattern) def matches(i,j): # 匹配str的第i个字符和pattern的第j个字符是否相等 if i0: return False if pattern[j-1].: return True return str[i-1]pattern[j-1] dp[[False]*(m1) for _ in range(n1)] dp[0][0]True # 空字符串和空匹配符必然相同 for i in range(m1): for j in range(1,n1): # pattern为空时dp[j][0]为False所以不用遍历了 if pattern[j-1]*: dp[j][i]|dp[j-2][i] # ‘或’判别式忽略*和它前面的字符匹配0次 if matches(i,j-1): dp[j][i]|dp[j][i-1] # 如果str当前字符和*前面的字符匹配上了消耗str的一个字符但是pattern不变*号继续匹配匹配1次或多次 else: if matches(i,j): dp[j][i]|dp[j-1][i-1] # 如果当前不是*只要当前两个字符匹配就把状态从之前转移过来 return dp[-1][-1]NC54 三数之和给出一个有n个元素的数组SS中是否有元素a,b,c满足abc0找出数组S中所有满足条件的三元组。数据范围0≤n≤1000数组中各个元素值满足 ∣val∣≤100空间复杂度O(n2)时间复杂度 O(n2)注意三元组a、b、c中的元素必须按非降序排列。即a≤b≤c解集中不能包含重复的三元组。class Solution: def threeSum(self , num: List[int]) - List[List[int]]: # write code here num.sort() res[] if len(num)3: return [] for i in range(len(num)-2): #固定一个后移动另外两个指针同时排除相同的值 if i0 and num[i]num[i-1]: continue ji1 klen(num)-1 while jk: if num[i]num[j]num[k]0: res.append([num[i],num[j],num[k]]) while j1k and num[j]num[j1]: j1 while jk-1 and num[k]num[k-1]: k-1 j1 k-1 elif num[i]num[j]num[k]0: k-1 else: j1 return res