leetcode10正则表达式匹配

前言

持续更新了

正文

问题来源

本问题来自leetcode上的10题。

问题描述

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 * 。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

分析：

朴素的思想：暴力求解（回溯法）
想法是在当前正则匹配串处理位置上，判断正则匹配串后一位是否是星号。
1）如果为；
a）当前正则匹配串是点号，待匹配串在它的当前位置到结束位置都有可能能够匹配上，正则匹配串向后移动2个字符
b）当前正则匹配串是字符，待匹配串在它的当前位置直到正则匹配串当前所指字符不相等前都有可能能够匹配上，正则匹配串向后移动2个字符
2）如果不为；
a）当前正则匹配串是点号，两个串均向后移动一个位置
b) 当前正则匹配串是字符，并且当前待匹配串和当前正则匹配串相同，两个串均向后移动一个位置
3）以上都不满足，返回false

func isMatch(s string, p string) bool {
    return subMatch(s, p, 0, 0)
}

func subMatch(s, p string, si, pi int) bool {
	// 结束判断
    if si >= len(s) {
        if pi >= len(p) {
            return true
        }
        if pi + 1 < len(p) && p[pi+1] == '*' { //形如s:a p:ab*
            return subMatch(s,p,si, pi+2)
        }
        return false
    } else if pi >= len(p) {
        return false
    }
    if pi + 1 < len(p) && p[pi+1] == '*' {
        if p[pi] == '.' {
            if subMatch(s,p,si, pi+2) { //.*一个字符都不消费
                return true
            }
            for i := si; i < len(s); i++ { //可以尝试匹配到最后
                if subMatch(s,p,i+1, pi+2) {
                    return true
                }
            }
            return false
        } else {
            if subMatch(s,p,si, pi+2) { // x*一个字符都不消费(x为si所指字符)
                return true
            }
            for i := si; i < len(s) && s[i] == p[pi]; i++ { //匹配到不相等为止
                if subMatch(s,p,i+1, pi+2) {
                    return true
                }
            }
            return false
        }
    }
    if p[pi] == '.' || p[pi] == s[si] {
        return subMatch(s, p, si+1, pi+1)
    }
    return false // p[pi] != '.' && p[pi] != s[si]
}

动态规划解法

                                |--  f[i-1][j],  match(s[i],p[j])
          |--  if p[j] != '*' = |
          |                     |--  false, else
f[i][j] = |
          |                     |-- f[i-1][j]||f[i][j-2], match(s[i],p[j-1])
          |--       else      = |
                                |-- f[i][j-2], else
边界条件f[0][0] = true

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]bool, n+1)
    }
    match := func(i, j int) bool {
        if i == 0 {
            return false
        }
        if p[j-1] == '.' || s[i-1] == p[j-1] {
            return true
        }
        return false
    }
    dp[0][0] = true
    for i := 0; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] != '*' {
                if match(i, j) {
                    dp[i][j] = dp[i-1][j-1]
                } else {
                    dp[i][j] = false
                }
            } else {
                if match(i, j-1) { //*
                    dp[i][j] = dp[i-1][j] || dp[i][j-2]
                } else {
                    dp[i][j] = dp[i][j-2]
                }
            }
        }
    }
    return dp[m][n]
}

总结：

勤思考。

结语

不管怎么样好好加油。

leetcode 10 Regular Expression Matching

前言

正文