//
//  Solution10.hpp
//  Algorithm
//
//  Created by Pancf on 2019/12/10.
//  Copyright © 2019 Pancf. All rights reserved.
//

#ifndef Solution10_hpp
#define Solution10_hpp

#include <stdio.h>
#include <string>

using std::string;

class Solution10 {
/**
 Given an input string (s) and a pattern (p), 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).

 Note:

 s could be empty and contains only lowercase letters a-z.
 p could be empty and contains only lowercase letters a-z, and characters like . or *.
 Example 1:

 Input:
 s = "aa"
 p = "a"
 Output: false
 Explanation: "a" does not match the entire string "aa".
 Example 2:

 Input:
 s = "aa"
 p = "a*"
 Output: true
 Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
 Example 3:

 Input:
 s = "ab"
 p = ".*"
 Output: true
 Explanation: ".*" means "zero or more (*) of any character (.)".
 Example 4:

 Input:
 s = "aab"
 p = "c*a*b"
 Output: true
 Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
 Example 5:

 Input:
 s = "mississippi"
 p = "mis*is*p*."
 Output: false
 ================================================================================================
 Accept details:
 递归解法
 Runtime: 220 ms, faster than 12.22% of C++ online submissions for Regular Expression Matching.
 Memory Usage: 15.2 MB, less than 11.87% of C++ online submissions for Regular Expression Matching.
 DP解法
 Runtime: 4 ms, faster than 92.91% of C++ online submissions for Regular Expression Matching.
 Memory Usage: 8.8 MB, less than 69.49% of C++ online submissions for Regular Expression Matching.
 */
public:
    bool isMatch(string s, string p);
    static void test() {
        Solution10 s = Solution10();
        string s1 = "aa";
        string p1 = "a";
        string s2 = "aa";
        string p2 = "a*";
        string s3 = "ab";
        string p3 = ".*";
        string s4 = "aab";
        string p4 = "c*a*b";
        string s5 = "mississippi";
        string p5 = "mis*is*p*.";
        string s6 = "ab";
        string p6 = ".*c";
        printf("%d\n", s.isMatch(s1, p1));
        printf("%d\n", s.isMatch(s2, p2));
        printf("%d\n", s.isMatch(s3, p3));
        printf("%d\n", s.isMatch(s4, p4));
        printf("%d\n", s.isMatch(s5, p5));
        printf("%d\n", s.isMatch(s6, p6));
    }
};

#endif /* Solution10_hpp */