题目描述
Given an input string (s) and a pattern (p), implement 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).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
思路：
- *匹配前面字符的重复。动态规划匹配串，和模式串索引。记录匹配串和模式串，所有从0开始的子串的匹配。总长度dp[s+1]][p+1]。最小问题为，从匹配0个字符开始填，第一行容易填。
- p[j]为.或匹配了s[i] 则dp[i][j] = dp[i-1][j-1]
- p[j]为*：
- a*空匹配，dp[i][j] = dp[i][j-2]
- 为.*或者匹配，以下3情况，有一种情况匹配，则匹配：
- 多匹配：dp[i][j] = d[i-1][j]。（只是去掉s中的一个匹配字符，并未清掉a*对应的所有匹配）
- 单匹配：dp[i][j] = dp[i-1][j-2]（或者是dp[i][j-1]）
- 由以上递推关系，需要先将i=0行填好，再补上。匹配一个字符，模式会有多个a*。
细节：
- 防止取j-1时数组越界。
- p[j]为*，且p[j-1]匹配或不匹配时，a*匹配0个字符并不是同一种情况，因而都会有dp[i+1][j-1]的选项。
解：
package main
import "fmt"
func isMatch(s string, p string) bool {
sSlice := []rune(s)
pSlice := []rune(p)
dp := make([][]bool,len(s)+1)
for idx,_ := range dp{
dp[idx] = make([]bool,len(p)+1)
}
dp[0][0] = true
for i:=0;i<len(p);i++ {
if pSlice[i] == '*' {
dp[0][i+1] = dp[0][i-1]
}
}
for i:=0;i<len(s);i++{
for j:=0;j<len(p);j++{
if pSlice[j] == '.' || pSlice[j] == sSlice[i]{
dp[i+1][j+1] = dp[i][j]
}
if pSlice[j] == '*'{
if pSlice[j-1] == '.' || pSlice[j-1] == sSlice[i]{
//a*匹配1个或多个
dp[i+1][j+1] = dp[i+1][j]|| dp[i][j+1]||dp[i+1][j-1]
}else if j>0 {
dp[i+1][j+1] = dp[i+1][j-1]
}
}
}
}
return dp[len(s)][len(p)]
}
func main() {
s := ""
p := ".*"
res := isMatch(s, p)
fmt.Print(res)
}
