10.正则表达式匹配.go

/*
 * @lc app=leetcode.cn id=10 lang=golang
 *
 * [10] 正则表达式匹配
 *
 * https://leetcode-cn.com/problems/regular-expression-matching/description/
 *
 * algorithms
 * Hard (22.94%)
 * Likes:    471
 * Dislikes: 0
 * Total Accepted:    16.3K
 * Total Submissions: 71.3K
 * Testcase Example:  '"aa"\n"a"'
 *
 * 给你一个字符串 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
 *
 */

var m1 = "*"[0]
var m2 = "."[0]

func isMatch(s string, p string) bool {
	if len(p) == 0 {
		return len(s) == 0
	}
	// x*xx的情况，可以分为
	// 1. *=0，若p[2:]能匹配也ok
	// 2. s长度为0，不匹配
	// 3. s长度不为0，若s[0]!=p[0]，且p[0]不是百变符，那不匹配
	// 4. 在3的情况下，s[1:]和p匹配时可以让*号为0，也可以去匹配多个，所以要看s[1:]和p
	if len(p) > 1 && p[1] == m1 {
		return isMatch(s, p[2:]) || (len(s) > 0 && (s[0] == p[0] || p[0] == m2) && isMatch(s[1:], p))
	}
	// 非x*xx但p长度大于0，可以分为
	// 1. s长度为0，不匹配
	// 2. s长度不为0，若s[0]!=p[0]，且p[0]不是百变符，那不匹配
	// 3. 没有*号，那s[1:]和p[1:]不匹配也不行
	return len(s) > 0 && (s[0] == p[0] || p[0] == m2) && isMatch(s[1:], p[1:])
}