题解 | #正则表达式匹配#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @param pattern string字符串
 * @return bool布尔型
 */
func match(str string, pattern string) bool {
	// write code here
	// 这个判断条件表示： 
	// if len(pattern) == 0 && len(str) == 0  return true；即如果字符串和模式串完全匹配，返回 true；举例：abc abc
	// if len(pattern) == 0 && len(str) != 0  return false; 即如果模式串已经用完，此时字符串还需要去匹配模式串，返回 false；举例：abc ab
	if len(pattern) == 0 {
		return len(str) == 0
	}

	// 这里判断主要为了要使用 pattern[1]，所以为了防止越界我们作提前判断
	if len(pattern) == 1 {
		return len(str) == 1 && (str[0] == pattern[0] || pattern[0] == '.')
	}

	if pattern[1] == '*' {
		// 一. 如果第二个字符为 '*' 并且第一个字符匹配上，那么有三种状态可以转移
		//  1.* 表示前一个字符出现 0 次 2. * 表示前一个字符继续出现 3. * 表示前一个字符仅出现一次
		if len(str) > 0 && (pattern[0] == str[0] || pattern[0] == '.') {
			return match(str, pattern[2:]) || match(str[1:], pattern) || match(str[1:], pattern[2:])
		}

		// 二. 如果第一个字符没有匹配上，那么跳过模式串的前 2 个字符；举例：aaa b*aaa
		return match(str, pattern[2:])
	}

	// 正常匹配情形 但是为了防止越界，需要判断 str 的长度是否大于 0，如果不做判断，访问 str[0] 会 panic
	if len(str) > 0 && (pattern[0] == str[0] || pattern[0] == '.') {
		return match(str[1:], pattern[1:])
	}

	return false
}

最麻烦的情况就是匹配穿第二个字符是 '*'，因为它可以表示它前面的字符出现 0 次~多次；

比如 a* 它可以表示 null 、a、aa、aaa ... ，因此我们需要确定这种情况下的状态转移；

在第二个字符为 '*' 时，也可以进一步分成两种情况：第一种是字符串第一个字符和模式串第一个字符匹配时，第二种情况是不匹配时；

当两个字符串首字符匹配时，有三种选择，第一种是让 * 表示前面的字符出现 0 次，直接跳过 a* ，使用模式串后面部分匹配 str；

第二种是让 * 表示前面的字符只出现 1 次，此时 a* 就表示 a，那么匹配上首字符，str 往后移动一个位置，pattern 往后移动两个位置（因为它使用 a* 代表一个 a）；第三种情况就是让 * 表示前面的字符出现多次，让首字符继续匹配 str 后一个位置的字符，此时 str 移动，pattern 不需要移动。

而当两个字符串首字符不匹配时，移动模式串，使用模式串后面部分继续匹配字符串；比如 aaa b*aaa。

上面的代码中，len(str) > 0 && (pattern[0] == str[0] || pattern[0] == '.') 重用了很多次，所以这部分可以优化一下：

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @param pattern string字符串
 * @return bool布尔型
 */
func match( str string ,  pattern string ) bool {
    // write code here
	if len(pattern) == 0 {
		return len(str) == 0
	}
	
	firstMatch := len(str) > 0 && (str[0] == pattern[0] || pattern[0] == '.')
	
	// 这里判断主要是后面要使用到 pattern[1]，这里提前作越界判断
	if len(pattern) == 1 {
		return len(str) == 1 && firstMatch
	}

	if pattern[1] == '*' {
		// 如果第二个字符为 '*' 并且第一个字符匹配上，那么有三种状态可以转移
		// 1. * 表示前一个字符出现 0 次 2. * 表示前一个字符继续出现 3. * 表示前一个字符仅出现一次
		if firstMatch {
			return match(str, pattern[2:]) || match(str[1:], pattern) || match(str[1:], pattern[2:])
		}
		// 如果第一个字符没有匹配上，那么跳过模式串的前 2 个字符
		return match(str, pattern[2:])
	}
	
	// 正常匹配情形 但是为了防止越界，需要判断 str 的长度是否 > 0
	if firstMatch {
		return match(str[1:], pattern[1:])
	}

	return false
}