leetcode-10. 正则表达式匹配(DFS)

2023-02-06 35

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

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

正则表达式

正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

目的：

1.判断给定的字符串是否符合正则表达式的过滤逻辑（称作“匹配”）：

2.可以通过正则表达式，从字符串中获取我们想要的特定部分。

思路

1.正常情况下,我们只需要一一对比，s[i] == p[j] || p[j] == ‘.’

2.当p[j]为‘ * ’时，我们要分两种情况讨论：

- s[i] != s[i + 1]时，我们则需要跳过p[j]，去和p[j + 1]匹配

- s[i] == s[i + 1]时，我们则需要跳过s[i]，去和s[i + 1]匹配，一直到与前一位不同

代码实现

func isMatch(s string, p string) bool {
    if len(p) == 0{
        if len(s) == 0{
            return true
        }
        return false
    }
    //记录当前匹配字符串不为空并且当前可以两两匹配
    f := (len(s) != 0) && (s[0] == p[0] || p[0] == '.')
    //判断下一位是否为*
    if len(p) >= 2 && p[1] == '*'{
        //匹配零个或多个前面的那个元素
        return isMatch(s, p[2:]) || (f && isMatch(s[1:], p))
    }else{
        //两两匹配
        return f && isMatch(s[1:], p[1:])
    }
}

leetcode-10. 正则表达式匹配(DFS)

正则表达式

目的：

思路

代码实现

热门文章

最新文章

相关电子书