题目链接：https://leetcode.cn/problems/regular-expression-matching/
正则表达式
正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。
目的：
1.判断给定的字符串是否符合正则表达式的过滤逻辑（称作“匹配”）：
2.可以通过正则表达式，从字符串中获取我们想要的特定部分。
思路
1.正常情况下,我们只需要一一对比，s[i] == p[j] || p[j] == ‘.’
2.当p[j]为‘ * ’时，我们要分两种情况讨论：
- s[i] != s[i + 1]时，我们则需要跳过p[j]，去和p[j + 1]匹配
- s[i] == s[i + 1]时，我们则需要跳过s[i]，去和s[i + 1]匹配，一直到与前一位不同
代码实现
func isMatch(s string, p string) bool { if len(p) == 0{ if len(s) == 0{ return true } return false } //记录当前匹配字符串不为空并且当前可以两两匹配 f := (len(s) != 0) && (s[0] == p[0] || p[0] == '.') //判断下一位是否为* if len(p) >= 2 && p[1] == '*'{ //匹配零个或多个前面的那个元素 return isMatch(s, p[2:]) || (f && isMatch(s[1:], p)) }else{ //两两匹配 return f && isMatch(s[1:], p[1:]) } }
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)