Leetcode No.10 regular expression matching

One 、 Title Description

Give you a string  s  And a character rule  p, Please come to realize a support '.'  and  '*'  Regular expression matching .

'.' Match any single character
'*' Match zero or more previous elements
Match , Is to cover   Whole   character string  s Of , Instead of partial strings .

explain :

s  May is empty , And contains only from  a-z  Lowercase letters of .
p  May is empty , And contains only from  a-z  Lowercase letters of , As well as the character  .  and  *.
Example 1:

Input :
s = "aa"
p = "a"
Output : false
explain : "a" Can't match "aa" Whole string .
Example 2:

Input :
s = "aa"
p = "a*"
Output : true
explain :  because '*' Represents the element that can match zero or more preceding elements , The element in front of here is 'a'. therefore , character string "aa" Can be regarded as 'a' I repeated it once .
Example  3:

Input :
s = "ab"
p = ".*"
Output : true
explain : ".*" Means zero or more can be matched （'*'） Any character （'.'）.
Example 4:

Input :
s = "aab"
p = "c*a*b"
Output : true
explain :  because '*' Represents zero or more , here 'c' by 0 individual , 'a' Be repeated once . So you can match strings "aab".
Example 5:

Input :
s = "mississippi"
p = "mis*is*p*."
Output : false

Two 、 Ideas

First convert the string into a pointer

1、 If p It's empty ,s Null match ,s Non null mismatch ;
2、s Non empty ,p == s || p == '.' Match the first character when ;
3、(p+1) != '', Then recursively determine whether the rest match first_match && isMatch(++s, ++p)
4、(p+1) == '*', There are two matching cases ：
① * matching 0 Characters ,s Match the rest , namely isMatch(s, p+2)
② * matching 1 Characters , Keep using p Match the rest s, namely first_match && isMatch(s+1, p)

3、 ... and 、 Code

Log in and copy

class Solution {
public:
    bool isMatch(string s, string p) {
        const char *s2 = s.c_str();
        const char *p2 = p.c_str();
        if (!*p2) return !*s2;
        bool first_match = *s2 && (*s2 == *p2 || *p2 == '.');
        if (*(p2+1) == '*') {
            return isMatch(s2, p2+2) || (first_match && isMatch(++s2, p2));
        }
        else {
            return first_match && isMatch(++s2, ++p2);
        }
    }
};
      

       
1.
       
2.
       
3.
       
4.
       
5.
       
6.
       
7.
       
8.
       
9.
       
10.
       
11.
       
12.
       
13.
       
14.
       
15.