leetcode有不少双字符串类型的题目，比如 “给两个字符串，判断 str1 -> str2 需要的最少改变次数”，“给两个字符串，判断 str2 是否是 str1 的正则表达”。
对于这类双字符串类型的题目，有一个常见的思路是：将一个字符串作为行、一个字符串作为列，然后进行dfs、dp，且这类题也是经典的dp问题。
以 leetcode 10: 正则表达式匹配 为例：给定两个字符串，判断string p 是否是 string s 的正则匹配。
解法一：dfs + buffer
dfs是最符合思考过程的算法模式，因此 dfs+buffer 即能够达到和 dp 一样的时间复杂度，同时在思维上也相对更好思考。
定义递归函数 func dfs(s, p string, si, pi int, buffer [][]int) bool，意思是：s[..i]与 p[...j] 是否能够正则匹配。中间结果使用buffer来记录，其中 buffer[si][pi] = -1 表示 false，buffer[si][pi] = 1 表示 true，等于0表示该组合还未看过。
base case
递归函数，首先考虑其base case。对于本题，base case应考虑两种情况：1. pi == 0（p为空串）；2. si == 0（s为空串）。
若pi == 0（p为空串），则只有当 si == 0（s也为空串）时才为true，其他均为false。
若si == 0（s为空串），则需要分情况讨论对应的 pi。若 p[pi-1] != ''，则一定无法匹配，返回false；若p[pi-1] == ''，则应看结果 dfs(s, p, si, pi-2, buffer)。
于是有：
// base case
if pi == 0 {
if si == 0 {
buffer[si][pi] = 1 // true
} else {
buffer[si][pi] = -1 // false
}
return buffer[si][pi] == 1
}
if si == 0 {
if p[pi-1] != '*' {
buffer[si][pi] = -1 // false
} else {
if dfs(s, p, si, pi-2, buffer) {
buffer[si][pi] = 1 // true
} else {
buffer[si][pi] = -1 // false
}
}
return buffer[si][pi] == 1
}
recursive rule
接着考虑recursive rule。由于*的特殊性，因此从大类上分为两类：1. p[pi-1] != ''；2. p[pi-1] == ''。
若 p[pi-1] != '*'。1. p[pi-1] == s[si-1] || p[pi-1] == '.'，则需要看 dfs(s, p, si-1, pi-1, buffer)的结果；否则直接返回false。
若 p[pi-1] == '*'。1. p[pi-2] == s[si-1] || p[pi-2] == '.'，则需要看 dfs(s, p, si, pi-2, buffer) || dfs(s, p, si-1, pi-2, buffer) || dfs(s, p, si-1, pi, buffer) 的结果；否则需要看 dfs(s, p, si, pi-2, buffer) 的结果。
于是有
// si, pi != 0
if p[pi-1] != '*' {
if p[pi-1] == s[si-1] || p[pi-1] == '.' {
if dfs(s, p, si-1, pi-1, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
} else {
buffer[si][pi] = -1
}
} else {
if p[pi-2] == s[si-1] || p[pi-2] == '.' {
if dfs(s, p, si, pi-2, buffer) ||
dfs(s, p, si-1, pi-2, buffer) ||
dfs(s, p, si-1, pi, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
} else {
if dfs(s, p, si, pi-2, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
}
}
full code
func isMatch(s string, p string) bool {
buffer := make([][]int, len(s)+1)
for i := range buffer {
buffer[i] = make([]int, len(p) + 1)
}
return dfs(s, p, len(s), len(p), buffer)
}
// s[...si] matches p[...pi]?
// buffer[si][pi] = 1 if true
// buffer[si][pi] = -1 if false
func dfs(s, p string, si, pi int, buffer [][]int) bool {
if buffer[si][pi] != 0 {
return buffer[si][pi] == 1
}
// base case
if pi == 0 { // pattern == ""
if si == 0 { // s == ""
buffer[si][pi] = 1
} else { // s != ""
buffer[si][pi] = -1
}
return buffer[si][pi] == 1
}
if si == 0 { // s == "" && pattern != ""
if p[pi-1] == '*' && dfs(s, p, si, pi - 2, buffer){
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
return buffer[si][pi] == 1
}
// si, pi != 0
if p[pi-1] != '*' {
if p[pi-1] == s[si-1] || p[pi-1] == '.' {
if dfs(s, p, si-1, pi-1, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
} else {
buffer[si][pi] = -1
}
} else {
if p[pi-2] == s[si-1] || p[pi-2] == '.' {
if dfs(s, p, si, pi-2, buffer) ||
dfs(s, p, si-1, pi-2, buffer) ||
dfs(s, p, si-1, pi, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
} else {
if dfs(s, p, si, pi-2, buffer) {
buffer[si][pi] = 1
} else {
buffer[si][pi] = -1
}
}
}
return buffer[si][pi] == 1
}
dp
dfs+记忆化搜索 向 dp 的转换，只需要将 base case 与 recursive rule 通过直接操作buffer写出来即可。
