regular expression matching_valid parentheses_leetcode 10

Implement regular expression matching with support for'.'and'*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

核心思路是一个动态规划，dp[i][j]表示字串 s[i...len(s)], p[j...len(p)] 是否可以匹配。regular expression matching

状态转移方程如下：

dp[i][j] =

c1. p[j1] != '*'时 if s[i] == p[j] dp[i][j] = dp[i1][j1]

else dp[i][j] = false

c2 p[j1] == '*'时 (这个情况下，要扩展 *, dp[i][j] 从拓展的情况下，选择一个是真的结果）

if( s[i] == p[j] || p[j] == '.' && (*s) != 0) 当s[i] 和 p[j] 一样的时候，例如 aba, a*b这个时候，i = 0, j = 0, 自然可以匹配a a

如果p[j] == . 因为他可以匹配任何字符，所以和相等关系有基本一样的方式。

并且每一步匹配都要递增 i 的，如果有成立的，则返回true，否则到匹配终了，返回通配符匹配完成后的结果。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-39692-1.html