我最近复习一道困难程度的算法题,发现了许多有趣之处。在借鉴了他人解法后,发现从最简单的情况反推到原题是一种解锁新进阶的感觉。从递归到动态规划,思维上一步一步递进,如同一部跌宕起伏的小说,记录下来和诸君共赏之。
题目如下:
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 说明: s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。 示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2: 输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。 示例 3: 输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。 示例 4: 输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。 示例 5: 输入: s = "mississippi" p = "mis*is*p*." 输出: false 来源:力扣(LeetCode)这是一道关于字符串匹配的问题,其中匹配字符串里面可能含有两种特殊符号「.」和「*」。
说时候刚拿到这道题的时候我很懵逼,直接动手分析到带有「*」符号的时候,感觉不同情况挺难分析下去的,甚至陷入了思维的僵局。
如果能让问题简化一下该多好呀,没错,如果我们把问题变成我们以前做过的问题或者容易做的问题,是否能从中发现新的思路?
假设问题变成:求两个纯字符串进行匹配。实现代码可以如下:
package main func isMatch(text string, pattern string) bool { if pattern == "" { if text != "" { return false } else { return true } } first_match := false if pattern[0] == text[0] { first_match = true } return first_match && isMatch(text[1:], pattern[1:]) } func main() { text := "abc" pattern := "ab" isMatch(text, pattern) }这里用到了递归,之所以这么处理,是为了后续迭代。
那么如果再增加一个条件,把「.」符号加上,如果是带有「.」符号的字符串去匹配一段字符串呢?
需要在实现的时候考虑第一个字节是否是该特殊符号
func isMatch2(text string, pattern string) bool { if pattern == "" { if text != "" { return false } else { return true } } first_match := false if pattern[0] == text[0] || pattern[0] == '.' { first_match = true } return first_match && isMatch2(text[1:], pattern[1:]) }能解决「.」符号的情况,针对「*」符号的情况,我们可以进一步思考。
可能性:
1.匹配0次。
2.匹配1次。
具体代码如下:
这段代码都是用递归实现的,但是递归的时间复杂度消耗更大,完全可以考虑将每一次递归的结果保存下来,于是我们又可以往动态规划的方向思考。
选择dp保存结果,dp[i][j]表示前i个字符串被j个字节pattern匹配的结果。
反思:还有无更好的解法呢?比如把循环放到外层,而不是封装成dp函数?