正则表达式

发表于 | 分类于 | 浏览 次
字数统计: 813 | 阅读时长 ≈ 3

    最近项目中需要用到正则表达式对文件名进行匹配。在上传文件时，如果文件名中含有连续的相同字母或数字，则不允许上传。并且文件名中必须含有设备型号。

正则表达式描述了字符串的匹配模型。

  • +：表示前面的字符必须出现至少一次（1次或多次）
    eg：runoo+b可以匹配runoob、runooob、runoooob
  • ：表示前面的字符可以不出现，也可以出现一次或多次（0次，1次或多次）
    eg：runoo\    b可以匹配runob、runoob、runooob
  • ？：表示前面的字符出现0次或1次。
    eg：do(es)?可以匹配”do”或”does”
    eg：colou?r 可以匹配 color 或者 colour

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

链接：https://leetcode-cn.com/problems/regular-expression-matching

【分析】

需要明确一点：s=a，p=ca，返回为true。因此`c是放在一起看的，c*`表示有0个c，或者多个c。

s：真实的字符串
p：带有正则表达式的字符串
看p是否能匹配s

定义dp状态
dp[i][j]表示s的前i个字符[0,i)是否能匹配p的前j个字符[0,j)。这里是左闭右开，也就是dp[i][j]比较的是s[i-1]和p[j-1]，有2种关系

  • s[i-1]==p[j-1]
  • s[i-1]!=p[j-1]
    • p[j-1]是a~z的一个字母
    • p[j-1]是*
    • p[j-1]是.

下面分别考虑以上情况

  • s[i-1]==p[j-1]
    dp[i][j]=dp[i-1][j-1]

  • s[i-1]!=p[j-1] 且p[j-1]=*
    *表示前面的字符是0个或多个。*前面的字符为p[j-2]，看是否和s[i-1]相等

    • p[j-2]==s[i-1]或p[j-2]=.
      *表示p[j-2]可以是0个或多个
      (1) 当*取0个时，例如s=aab,b=aabb*，虽然s[i-1]==p[j-2]，但由于dp[i][j-2]已经匹配了，所以此时的dp[j-2]是多余的，所以*取0。此时dp[i][j]=dp[i][j-2]
      (2) 当*取1个字符时， 例如s=aab,b=aab*，dp[i][j]=dp[i][j-1]
      (3) 当*取多个字符时，例如s=aabb,b=aab*，dp[i][j]=dp[i-1][j]
  • s[i-1]!=p[j-1] 且p[j-1]=.
    .是万能字符，可以把.变成s[i-1]的字符，dp[i][j]=dp[i-1][j-2]
  • s[i-1]!=p[j-1] 且p[j-1]是普通字符
    那s的前i个字符和p的前j个字符就不匹配了，dp[i][j]=False

初始化dp

  • dp[0][0]=True
  • dp[0][j]:表示s的前0个字符和p的前j个字符匹配情况，如果p[j-1]是*，则可以把p[j-1]和p[j-2]的字符删去，只有dp[0][j-2]为true，才能让dp[0][j]为true
    if p[j-1]=='*' and dp[0][j-2]
    -
打赏
0%