该题目来源于牛客网《剑指offer》专题。
请实现一个函数用来匹配包括 . 和 * 的正则表达式。模式中的字符.
表示任意一个字符,而 * 表示它前面的字符可以出现任意次(包含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配。
Go语言实现:
func match(str, pattern string) bool {
if str == "" || pattern == "" {
return false
}
return matchHandler([]byte(str), 0, []byte(pattern), 0)
}
func matchHandler(s []byte, sIndex int, p []byte, pIndex int) bool {
sLength := len(s)
pLength := len(p)
//s结束,p也结束,匹配成功
//字符串的所有字符匹配整个模式,所以a与aa不匹配,所以是==
if sIndex == sLength && pIndex == pLength {
return true
}
//s未结束,p结束 或者 s结束,p未结束,匹配失败
if (sIndex != sLength && pIndex == pLength) || (sIndex == sLength && pIndex != pLength) {
return false
}
//第二位是*
if pIndex+1 < pLength && string(p[pIndex+1]) == "*" {
//第一位匹配
if (sIndex != sLength && s[sIndex] == p[pIndex]) || (sIndex != sLength && string(p[pIndex]) == ".") {
return matchHandler(s, sIndex, p, pIndex+2) || //aa匹配a*aa
matchHandler(s, sIndex+1, p, pIndex+2) || //aa匹配a*a
matchHandler(s, sIndex+1, p, pIndex) //aa匹配a*
} else { //第一位不匹配
return matchHandler(s, sIndex, p, pIndex+2)
}
}
//第二位不是*,一一匹配
if (sIndex != sLength && s[sIndex] == p[pIndex]) || (sIndex != sLength && string(p[pIndex]) == ".") {
return matchHandler(s, sIndex+1, p, pIndex+1)
}
return false
}