regular expression matching_longest common prefix_palindrome

【LeetCode】10. Regular Expression Matching

Regular Expression Matching

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

比较与Wildcard Matching的关系。

在Wildcard Matching中的'?'与此题的'.'一致。

但是Wildcard Matching中'*'本身代表通配符，而此题'*'代表前一个字符重复0或若干次。

解题过程如下：

1、考虑特殊情况即*s字符串或者*p字符串结束。

（1）*s字符串结束，要求*p也结束或者间隔‘*’ （例如*p="a*b*c*……"），否则无法匹配

（2）*s字符串未结束，而*p字符串结束，则无法匹配

2、*s字符串与*p字符串均未结束

（1）*(p+1)字符不为'*'，则只需比较*s字符与*p字符，若相等则递归到*(s+1)字符串与*(p+1)字符串的比较，否则无法匹配。

（2）*(p+1)字符为'*'，则*p字符可以匹配*s字符串中从0开始任意多（记为i）等于*p的字符，然后递归到*(s+i+1)字符串与*(p+2)字符串的比较，

只要匹配一种情况就算完全匹配。regular expression matching

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