本科专业 网站开发,不懂开发如何建设网站,阿里云建站和华为云建站哪个好,蓝色网站导航1 题干内容 请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符#xff0c;而*表示它前面的字符可以出现任意次#xff08;包含0次#xff09;。
在本题中#xff0c;匹配是指字符串的所有字符匹配整个模式。
例如#xff0c;字符串aaa与模式a.a…1 题干内容 请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符而*表示它前面的字符可以出现任意次包含0次。
在本题中匹配是指字符串的所有字符匹配整个模式。
例如字符串aaa与模式a.a和ab*ac*a匹配但是与aa.a和ab*a均不匹配。 2 题意解析 匹配是指完全匹配即aaa与aaaa不匹配只有aaa与aaa才能说是匹配。
b*可以理解是也可以是bbbbbb*例如ab*ac*a可以理解为aaa也可以理解为abaa或者abaca。 3 解题思路 字符串strA, 模式串patternB
(1)patternB[j1] ! *
当strA[i] patternB[j]或者patternB[j] . and i len(strA)如果strA[i1] ! patternB[j1], 返回False如果strA[i1] patternB[j1]进行下一轮比较
当strA[i] ! patternB[j] and patternB[j] ! . 直接返回Flase (2)patternB[j1] * 当strA[i] patternB[j]或者patternB[j] . and i len(strA) 1)i不变模式串 j j 2 2)j不变字符串 i i 1 3i i 1 j j 2 当strA[i] ! patternB[j] and patternB[j] ! . 1)i不变模式串 j j 2 4 具体代码 def matchReg(strA: str, patternB: str, i: int 0, j: int 0) - bool:if i len(strA) and j len(patternB): # 完全匹配return Trueif i len(strA) and j len(patternB) or (i len(strA) and j len(patternB)):return Falseif (j1) len(patternB) and patternB[j1] *:if (patternB[j] . and i len(strA)) or (strA[i] patternB[j]):return matchReg(strA, patternB, i, j 2) or matchReg(strA, patternB, i 1, j) or matchReg(strA, patternB, i 1, j 2)else:return matchReg(strA, patternB, i, j 2)if (patternB[j] . and i len(strA)) or (strA[i] patternB[j]):return matchReg(strA, patternB, i 1, j 1)return False GitHub链接https://github.com/miaomiaoqiushui/Algorithm/blob/master/1_%E5%89%91%E6%8C%87Offer/53_%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D.ipynb 转载于:https://www.cnblogs.com/liuzhen1995/p/10799234.html
