mplement regular expression matching with support for ‘.’ and ‘*’.
’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a”) → true
isMatch(“aa”, “.”) → true
isMatch(“ab”, “.”) → true
isMatch(“aab”, “ca*b”) → true
注:*这种情况下只是匹配到前一个字符
递归
func isMatch(s string, p string) bool {
if len(p)==0{
return len(s)==0
}
firstMatch:=s[0]==p[0]||p[0]=='.'
if len(p)>=2&&p[1]=='*'{
return isMatch(s,p[2:])||(firstMatch&&isMatch(s[1:],p))
}else{
return firstMatch&&isMatch(s[1:],p[1:])
}
动态规划
func isMatch(s string, p string) bool {
return dp(0,0,s,p)
}
func dp(i int,j int,s string,p string) bool{
var ret bool
if j==len(p){
ret= i==len(s)
}else if i<len(s){
firstMatch:=p[j]=='.'||s[i]==p[j]
if j+1<len(p)&&p[j+1]=='*'{
ret= dp(i,j+2,s,p)||(firstMatch&&dp(i+1,j,s,p))
}else{
ret=firstMatch&&dp(i+1,j+1,s,p)
}
}else{
if j+1<len(p)&&p[j+1]=='*'{
ret= dp(i,j+2,s,p)
}
}
return ret
}
错误答案 这种问题没法穷尽,代码直白些能累死
func isMatch(s string, p string) bool {
i:=0
j:=0
for i<len(s)&&j<len(p){
if p[j]=='*'||p[j]=='.'{
if p[j]=='.'{
if j+1<len(p)&&p[j+1]=='*'{
if j+2<len(p){
tmpj:=j+2
for ;tmpj<len(p);tmpj++{
if p[tmpj]!='*'&&p[tmpj]!='.'{
break
}else {
}
}
if tmpj==len(p){
return true
}else {
j=tmpj
tmpi:=i
var sig1 bool=false
for ;tmpi<len(s);tmpi++{
if s[tmpi]==p[j]{
i=tmpi
sig1=true
break
}
}
if tmpi==len(s)-1&&!sig1{
return false
}
}
}else {
return true
}
}else{
i++
j++
}
}else if p[j]=='*'{
if p[j-1]=='*'{
i++
j++
}
}
}else{//p是正常字符
if j+1<len(p)&&p[j+1]=='*'{
if s[i]==p[j]{
tmp:=i
for i<len(s)&&s[tmp]==s[i]{
i++
}
if j+2<len(p){
if p[j+2]==p[j]{
i--
}
j+=2
}else{
j++
}
}else{
j+=2
}
}else{
if s[i]!=p[j]{
return false
}else {
i++
j++
}
}
}
}
if i<len(s){
return false
}
if j<len(p){
m:=j
for ;m<len(p);m++{
if p[m]!='*'{
break
}
}
if m==len(p){
return true
}else{
return false
}
}
return true
}