LeetCode10-正则表达式匹配

题目链接：LeetCode10

一道应用场景十分广泛的题目，可以用动态规划来做，也可以用有限状态机来做。但是方法二我还没学会实现方法，挖个坑，后面来填。

题意

• 给定两个字符串，一个是待匹配的字符串 s ，一个是模式串 p ，要求判断 s 是否是 p 的正则匹配。
• 题目环境下的正则匹配只包含 "a*" 和 "." ，这两种特殊匹配，不考虑括号和或运算“|”。

思路

• 定义bool数组：dp[i][j] 表示 s[0~i] 与 p[0~j] 是否能够匹配。
• 当 p[j]=='.' 或 s[i]==p[j] 时，用 dp[i][j]=dp[i-1][j-1] 来表示能够进行匹配。
• 当 p[j]=='*' 时，因为正则表达式中，字符+“*” 可以表示用该字符匹配任意非负数个字符，就会有匹配0个字符，和匹配正数个字符的两种情况。
  • 用 dp[i][j] = dp[i][j] || dp[i][j-2]，来表示不利用该字符进行匹配的情况。
  • 用 dp[i][j] = dp[i][j] || dp[i-1][j]，来表示利用该字符进行匹配的情况。
    • 这一步实际上用了递推式来化简了转移方程，可以用s="aaaaa"，p=“a*”来对该转移式进行更深入的了解。

代码（Golang）

func isMatch(s string, p string) bool {    m, n := len(s), len(p)    //判断两字符是否匹配，把直接相等和p[j]=='.'两种情况考虑进来，封装成函数    matches := func(i, j int) bool { if i == 0 {     return false } if p[j-1] == '.' {     return true } return s[i-1] == p[j-1]    }    //f为动态规划的数组    f := make([][]bool, m + 1)    for i := 0; i < len(f); i++ { f[i] = make([]bool, n + 1)    } //两个空串可以直接匹配    f[0][0] = true    for i := 0; i <= m; i++ { for j := 1; j <= n; j++ {     if p[j-1] == '*' {  f[i][j] = f[i][j] || f[i][j-2]  if matches(i, j - 1) {      f[i][j] = f[i][j] || f[i-1][j]  }     } else if matches(i, j) {  f[i][j] = f[i][j] || f[i-1][j-1]     } }    }    return f[m][n]}