首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配
  • 热度指数:90543 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次(包含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 '*'。
3.
4.


示例1

输入

"aaa","a*a"

输出

true

说明

中间的*可以出现任意次的a,所以可以出现1次a,能匹配上              
示例2

输入

"aad","c*a*d"

输出

true

说明

因为这里 c 为 0 个,a被重复一次, * 表示零个或多个a。因此可以匹配字符串 "aad"。              
示例3

输入

"a",".*"

输出

true

说明

".*" 表示可匹配零个或多个('*')任意字符('.')              
示例4

输入

"aaab","a*a*a*c"

输出

false
class Solution:
def match(self, str: str, pattern: str) -> bool:
n1, n2 = len(str), len(pattern)
dp = [[False]*(n2+1) for _ in range(n1+1)]
dp[0][0] = True
for j in range(2, n2+1):
if pattern[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, n1+1):
for j in range(1, n2+1):
if pattern[j-1] == '.' or pattern[j-1] == str[i-1]:
# pattern当前字符为'.'或与str当前字符相同,对应字符直接匹配,结果取决于前面的字符串是否匹配
dp[i][j] = dp[i-1][j-1]
elif j >= 2 and pattern[j-1] == '*':
# 如果pattern当前字符为'*'
if pattern[j-2] == '.' or pattern[j-2] == str[i-1]:
# 当前字符能匹配上的只有两种情况:
# 1:pattern尾部为'.*',那么对应字符可以匹配任意情况,包括空字符
# 该种情况对应字符匹配上了,有两种情况:
# 1):'abc'和'a.*',此时dp[i][j] = dp[i-1][j],即考虑和'.*'的前面是否和str对应部分匹配
# 2):'a'和'a.*',此时dp[i][j] = dp[i][j-2], 事实上1)会转化为这种情况
# 2:pattern[j-2]和str尾部的字母可以匹配上
# 该种情况对应字符匹配上了,有一种情况:'abcc'和'abc*',此时dp[i][j] = dp[i-1][j],而同理dp[i-1][j] = dp[i-2][j],转化为'ab'和'abc*'
dp[i][j] = dp[i-1][j] or dp[i][j-2]
else:
dp[i][j] = dp[i][j-2]
return dp[n1][n2]
发表于 2023-09-20 15:45:29 回复(0)
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        import re
        return re.match(f'^{pattern}$',str) is not None

发表于 2023-09-05 22:06:44 回复(0)
面向规则编程,倒在了最后一组数据上,被 '.*' 坑了,过了34组,摆了
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        m = len(str)
        n = len(pattern)
        i,j = m-1,n-1
        flag = False
        while i>=0 and j>=0:
            flag = False
            if pattern[j]=='*':
                j -= 1
                if str[i]!=pattern[j]and pattern[j]!='.':
                    j -= 1
                    continue
                while i>=0 and (str[i]==pattern[j]&nbs***bsp;pattern[j]=='.'):
                    i -= 1
                j -= 1
                flag = True
                continue
            if str[i]==pattern[j]&nbs***bsp;pattern[j]=='.':
                i -= 1
                j -= 1
                continue
            if str[i] != pattern[j]:
                return False
        print(i,j)
        if i<0 and j<0:
            return True
        if i>=0:
            return False
        while j>=0:
            if pattern[j]=='*':
                j -= 2
            else:
                break
        if j<0:
            return True        
        from collections import Counter
        counter = Counter(pattern[:j+1])
        chars = counter.keys()
        counts = counter.values()
        print(counter)
        if '*' in chars:
            if sum(counts) == 2*counter['*']:
                return True
            else:
                return False
        if len(chars)>1:
            return False
        if not flag:
            return False
        lenlast = 1
        for i in range(1,m):
            if str[i]==str[i-1]:
                lenlast += 1
            else:
                break
        print(lenlast)
        if lenlast<counter[str[0]]:
            return False
        else:
            return True
            


发表于 2023-04-18 15:26:39 回复(0)
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        #分别用n和m来表示str和pattern的长度
        n = len(str)
        m = len(pattern)
        
        # num第i行第j列用来记录  str的前i个字符是否被pattern的前j个字符匹配
        # 使用动态规划的方法进行递推求解
        num = [[False for j in range(m+1)] for i in range(n+1)]
        
        for i in range(n+1):
            for j in range(m+1):
                
                # 如果pattern为空,而str不为空,显然无法匹配
                if (j == 0 and i != 0):
                    star_num = 0
                    num[i][j] = False
                    
                # 如果str为空,pattern不为空。这里要分情况,因为*可以表示零个字符
                # 如果*的个数是pattern字符个数的一半,即每个字符后面都跟一个*
                # 这种情况是可以匹配空字符串的,而在其他情况下无法匹配
                # 这里偷懒直接用一半来判断了,没有验证输入是否合法,
                # 例如出现连续的星号,或者星号出现在开头
                # 但因为验证数据都是正确的,所以不会有问题,实际使用还要考虑输入是否合法
                elif (i == 0 and j != 0):
                    # star_num用来记录pattern里*号的个数
                    star_num = 0
                    for index in pattern[0: j]:
                        if (index == '*'):
                            star_num += 1
                    if (star_num == j/2):
                        num[i][j] = True
                    else:
                        num[i][j] = False
                        
                # 如果str和pattern都为空, 可以匹配
                elif (i == 0 and j == 0):
                    num[i][j] = True
                    
                # 最复杂的情况,即str和pattern都不为空
                # 分几种情况讨论,考虑pattern的末尾为句号.  为*号  为正常字符
                # 注意因为num的索引i表示的是前i个字符,str表示第i个字符用的索引是i-1
                # 因此num的索引和pattern的索引间有减一的差别
                else:
                
                    # 如果pattern末尾为.号,则必定能匹配str的最后一位,因此num[i][j] = num[i-1][j-1]]
                    if (pattern[j-1] == '.'):
                        num[i][j] = num[i-1][j-1]
                      
                    
                    # 如果pattern的末尾为*号,继续分情况,倒数第二位为.号或者是普通字符
                    # (这里我没有验证j-2是否超出索引范围,因为合法的输入*前必有其他字符)
                    elif (pattern[j-1] == '*'):
                        
                        # 如果pattern倒数第二位为.号的话,则.*这两个字符可以匹配任意长的任意字符,
                        # 我们遍历str[0:i]前面的所有子字符串,如果存在一个能和pattern的前j-2字符pattern[:j-2]匹配,
                        # 那么str[0:i]和pattern[:j]就能匹配上,即num[i][j] = True
                        # 如果全不能匹配, 则num[i][j]为False
                        if (pattern[j-2] == '.'):
                            r = False
                            for k in range(i+1):
                                if (num[k][j-2] == True):
                                    r = True
                                    break
                            num[i][j] = r
                            
                        # 如果pattern倒数第二位为普通字符s, 假设str末尾有一串s(包括0个)
                        # 因为s*可以匹配任意多个s,我们从这串s中分开str
                        # 后面的部分用来匹配s*, 前面的部分用来匹配pattern[0: j-2] 
                        # 若存在一个前面的部分能匹配pattern[0: j-2] 则num[i][j] = True
                        # 如果每个分割后前面部分的str都不能匹配pattern[0: j-2],则为False
                        else:
                            k = i-1
                            while (k >= 0):
                                # 向前遍历直到str的字符不等于pattern倒数第二个,或者到0
                                if (str[k] != pattern[j-2]):
                                    break
                                # 如果存在一个前面的部分能匹配pattern[0: j-2] 
                                if (num[k+1][j-2] == True):
                                    break                                
                                k = k - 1 
 
                            num[i][j] = num[k+1][j-2]
    
    
                    # 如果pattern的末尾为普通字符,我们只需要验证str和pattern的末尾是否相等
                    # 若不相等,则为False,若相等,则num[i][j] = num[i-1][j-1]
                    else:
                        if (str[i-1] == pattern[j-1]):
                            num[i][j] = num[i-1][j-1]
                        else:
                            num[i][j] = False
        print(num)                    
        return num[n][m]
                                    

发表于 2022-04-14 13:06:21 回复(1)
import re


class Solution:
    def match(self, str: str, pattern: str) -> bool:
        # write code here
        m = re.match(pattern, str)
        if m:
            return m.group() == str
        return False

发表于 2022-03-12 20:04:14 回复(1)