剑指 Offer 19. 正则表达式匹配

剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含‘. ‘和‘*‘的正则表达式。模式中的字符‘.‘表示任意一个字符，而‘*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 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

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 ‘*‘。

思路

golang

采用动态规划的思想：
1.定义状态：dp[i][j]表示主串s的前i个字符和正则串p的前j个字符是否匹配
2.初始化dp数组：因为状态转移是从小到大，后面的状态需要依靠前面的状态判断。即需要初始化dp数组的首行和首列

• dp[0][0]表示s和p都是空串，很明显dp[0][0]=true
• 首列dp[i][0]=false(i!=0)，因为主串s不为空，而正则串p为空，明显不匹配
• 首行dp[0][j]比较特殊，s为空的情况下，p的偶数位为‘*‘的话是可以匹配上的，因为可以让‘*‘之前的字符出现次数为0

3.状态转移方程：因为已经初始化了首行和首列，s和p都从索引1开始匹配。下面开始分情况讨论：

• 正则串p的第j个字符为‘*‘，即p[j-1]==‘*‘

  1. 若dp[i][j-2]为true，那么dp[i][j]也为true
     即s的前i个字符和p的前j-2个字符匹配，且p的第j个字符为‘*‘，那么无论p的第j-1个字符是什么，令它出现0次，dp[i][j]就可以为true
  2. 若dp[i-1][j] && s[i-1]==p[j-2]条件为true，那么dp[i][j]也为true
     即s的前i-1个字符和p的前j个字符匹配，且s的第i个字符和p的第j-1个字符相等，让p的第j-1个字符多出现一次，s的前i字符和p的前j的字符就可以匹配了
  3. 若dp[i-1][j] && p[j-2]=‘.‘条件为true时，那么dp[i][j]也为true
     即s的前i-1个字符和p的前j个字符匹配，因为‘.‘字符可以匹配任意字符，那么s的第i个字符可以匹配p的第j-1个字符，令p的第j-1个字符多出现一次即可

  上述2，3可以合并为一个判断语句：dp[i-1][j] && s[i-1]==p[j-2] || dp[i-1][j] && p[j-2]==‘.‘

• 正则串p的第j个字符不为‘*‘，即p[j-1]!=‘*‘

  1. 若dp[i-1][j-1] && s[i-1]==p[j-1]条件为true，那么dp[i][j]也为true
     即s的前i-1个字符和p的前j-1个字符匹配，且s的第i个字符和p的第j个字符也相同
  2. 若dp[i-1][j-1] && p[j-1]==‘.‘条件为true，那么dp[i][j]也为true
     即s的前i-1个字符和p的前j-1个字符匹配，且p[j-1]=‘.‘，因为‘.‘可以匹配s[i]的任意字符串

  上述可以合并为一个判断语句：dp[i-1][j-1] && s[i-1]==p[j-1] || dp[i-1][j-1] && p[j-1] == ‘.‘

4.返回值：即dp[n][m]，主串的前n个字符和正则串的前m个字符是否匹配

func isMatch(s string, p string) bool {
	//获取主串s和正则串p的长度
	n, m := len(s), len(p)
	//创建dp数组
	dp := make([][]bool, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]bool, m+1)
	}
	//初始化dp数组
	dp[0][0] = true
	//初始化首行  首列直接为false
	for j := 2; j < m+1; j = j + 2 {
		dp[0][j] = dp[0][j-2] && p[j-1] == ‘*‘
	}

	//索引从1开始，分情况讨论
	for i := 1; i < n+1; i++ {
		for j := 1; j < m+1; j++ {
			//正则串p的第j个字符不为‘*‘，即p[j-1]!=‘*‘
			if p[j-1] != ‘*‘ {
				if dp[i-1][j-1] && s[i-1] == p[j-1] {
					dp[i][j] = true
				} else if dp[i-1][j-1] && s[i-1] == p[j-1] || dp[i-1][j-1] && p[j-1] == ‘.‘ {
					dp[i][j] = true
				}
			} else { //正则串p的第j个字符为‘*‘，即p[j-1]==‘*‘
				if dp[i][j-2] == true {
					dp[i][j] = true
				} else if dp[i-1][j] && s[i-1] == p[j-2] || dp[i-1][j] && p[j-2] == ‘.‘ {
					dp[i][j] = true
				}
			}
		}
	}

	return dp[n][m]
}

剑指 Offer 19. 正则表达式匹配

原文：https://www.cnblogs.com/zmk-c/p/14661850.html