golang力扣leetcode 10.正则表达式匹配

简介: golang力扣leetcode 10.正则表达式匹配

10.正则表达式匹配

10.正则表达式匹配

题解

题目:正则匹配,s主串,p正则表达式,返回能否匹配成功

思路:动态规划

1.定义dp[i][j]:在s串中前i位,p串中前j位,是否匹配成功
2.如果p能匹配当前字符,或者p为.  则dp[i][j] = dp[i-1][j-1]
3.如果p为*,则可以匹配0次或多次
4.如果dp[i][j-2]=true,说明匹配0次是成功的,匹配0次看前两位状态
5.如果不能匹配0次,说明需要匹配1次或多次,prev := p[j-2]
6.如果前一位字符prev匹配s的当前字符,或者prev=. ,则有机会匹配成功,如果不等于s的当前字符或不为. ,说明肯定不成功
7.有机会匹配成功dp[i][j] = dp[i-1][j],需要看前一个字符是否匹配成功

代码

func isMatch(s string, p string) bool {
  n := len(s) + 1
  m := len(p) + 1
  dp := make([][]bool, n)
  for i := range dp {
    dp[i] = make([]bool, m)
  }
  //空串匹配
  dp[0][0] = true
  //初始化边界,p与空串的匹配
  for i := 1; i < m; i++ {
    chP := p[i-1]
    if chP == '*' {
      dp[0][i] = dp[0][i-2]
    }
  }
  //dp开始
  for i := 1; i < n; i++ {
    chS := s[i-1]
    for j := 1; j < m; j++ {
      chP := p[j-1]
      //p能匹配当前字符,或者p为.
      if chP == chS || chP == '.' {
        dp[i][j] = dp[i-1][j-1]
      } else if chP == '*' { //p为前为*
        if dp[i][j-2] { //* 匹配0次,看前两位的状态
          dp[i][j] = true
        } else {
          prev := p[j-2]
          if prev == chS || prev == '.' {//p的前一位匹配当前字符,或p为.
            dp[i][j] = dp[i-1][j] //* 匹配一次或多次,看前一位的状态
          }
        }
      }
    }
  }
  return dp[n-1][m-1]
}
目录
相关文章
|
3月前
|
Go
golang力扣leetcode 437.路径总和III
golang力扣leetcode 437.路径总和III
36 0
|
3月前
|
Go 容器 SQL
【Golang Leetcode】总目录(Day1~100)
【Golang Leetcode】总目录(Day1~100)
475 1
【Golang Leetcode】总目录(Day1~100)
|
3月前
|
Go
golang力扣leetcode 494.目标和
golang力扣leetcode 494.目标和
29 0
|
3月前
|
Go
golang力扣leetcode 剑指Offer II 114. 外星文字典
golang力扣leetcode 剑指Offer II 114. 外星文字典
19 0
|
3月前
|
Go
golang力扣leetcode 第 295 场周赛
golang力扣leetcode 第 295 场周赛
36 0
|
6月前
|
存储 编译器 Go
Golang 语言的多种变量声明方式和使用场景
Golang 语言的多种变量声明方式和使用场景
32 0
|
6月前
|
缓存 编译器 Go
Golang 语言 vendor 在 GOPATH 和 Modules 中的区别
Golang 语言 vendor 在 GOPATH 和 Modules 中的区别
31 0
|
6月前
|
Go 数据中心 微服务
Golang 语言微服务的服务发现组件 Consul 的系统架构介绍
Golang 语言微服务的服务发现组件 Consul 的系统架构介绍
59 0
|
1月前
|
SQL 前端开发 Go
编程笔记 GOLANG基础 001 为什么要学习Go语言
编程笔记 GOLANG基础 001 为什么要学习Go语言
|
6月前
|
存储 JSON Go
Golang 语言 gRPC 服务怎么同时支持 gRPC 和 HTTP 客户端调用?
Golang 语言 gRPC 服务怎么同时支持 gRPC 和 HTTP 客户端调用?
71 0