给定一个字符串 (s
) 和一个字符模式 (p
)。实现支持 '.'
和 '*'
的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s
) ,而不是部分字符串。
说明:
s
可能为空,且只包含从 a-z
的小写字母。p
可能为空,且只包含从 a-z
的小写字母,以及字符 .
和 *
。示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输出: false
解题思路:
1,两个字符是否匹配只需要判断s[i]==p[j] ||p[j]=='.'
2,对于p[j]!='*'情况,p[j]以前的字符和s[i]以前的字符匹配条件是p[j]==s[i]&& p[j-1]和s[i-1]以前的字符都匹配
3,p[j]=='*'分3种情况
(1),p[j-1]匹配0次&&p[j-2]和s[i]匹配
(2),p[j-1]匹配1次(p[j-1]==s[i])&&p[j-2]和s[i-1]匹配
(3),p[j-1]匹配多次,p[j-1]==s[i]
A,p[j]和s[i-1]匹配
B,p[j-1]和s[i]匹配
4,用数组a[len(s)+1][len(p)+1]保存中间结果,其中a[i][j]表示s[0:i],p[0:j]是否匹配
5,由于c* 这种情况可以表示0次,所以方便起见,i和j长度各加1表示空串和对方匹配
6,初始条件特别多:
a[0][0]=true //空和空匹配
a[0][2*k]=a[0][2*(k-1)] && p[2*k-1]=='*' //c*这种,都匹配0次
func isMatch(s string, p string) bool {
if len(s) == 0 && len(p) == 0 {
return true
}
if len(p) == 0 {
return false
}
if len(s) == 0 {
if len(p)%2 != 0 {
return false
}
for i := 1; i < len(p); i += 2 {
if []byte(p)[i] != '*' {
return false
}
}
return true
}
bs := []byte(s)
bp := []byte(p)
a := make([][]bool, len(s)+1)
for i := 0; i < len(s)+1; i++ {
a[i] = make([]bool, len(p)+1)
}
a[0][0] = true
a[1][1] = match(bs[0], bp[0])
for j := 2; j < len(p)+1; j = j + 2 {
a[0][j] = a[0][j-2] && bp[j-1] == '*'
}
for i := 1; i < len(s)+1; i++ {
for j := 2; j < len(p)+1; j++ {
if bp[j-1] == '*' {
//0 1
a[i][j] = a[i][j-2] || (a[i-1][j-1] && match(bs[i-1], bp[j-2])) || (a[i][j-1] && match(bs[i-1], bp[j-2])) || (a[i-1][j] && match(bs[i-1], bp[j-2]))
} else {
a[i][j] = a[i-1][j-1] && match(bs[i-1], bp[j-1])
}
}
}
return a[len(s)][len(p)]
}
func match(a, b byte) bool {
return a == b || b == '.'
}
本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!