Topic describes

Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ‘*’.

  • ‘.’ matches any single character
  • The ‘*’ matches zero or more of the preceding elements

By matching, you want to cover the entire string S, not parts of the string.

The sample

Example 1: Input: s = “aa” p = “a” Output: false Description: “A” cannot match the entire string “aa”.

Example 2: Input: s = “aa” p = “a*” Output: true Explanation: Because ‘*’ stands for matching zero or more preceding elements, in this case the preceding element is ‘a’. Thus, the string “aa” can be treated as ‘a’ repeated once.

Example 3: Input: s = “ab” p = “.” Output: true Description: “.” Indicates that zero or more characters (‘.’) can be matched.

Example 4: Input: s = “aab” p = “CAB” Output: true Explanation: Because ‘*’ means zero or more, here ‘c’ is zero and ‘a’ is repeated once. So it matches the string “aab”.

Example 5: Input: s = “Mississippi” p = “misisp*.” output: false

Source: LeetCode link: leetcode-cn.com/problems/re…

implementation

bool isMatch(char * s, char * p)
{
    int sLen = strlen(s);
    int pLen = strlen(p);
    bool dp[sLen+1][pLen+1];     // Dynamically plan the array to see if the first I characters of s match the first j characters of p

    dp[0] [0] = true;   Dp [0][0]=true;
    for (int i = 1; i <= sLen; i++) {
        dp[i][0] = false;        Dp [I][0]=false;
    }
    for (int j = 1; j <= pLen; j++) {  // if x*y*z*... // if x*y*z*... (* = 0)
        if (j >= 2 && p[j- 1] = =The '*') {
            dp[0][j] = dp[0][j2 -];
        } else {
            dp[0][j] = false; }}// Walk from top to bottom, from right
    for (int i = 1; i <= sLen; i++) {
        for (int j = 1; j <= pLen; j++) {
            if ((p[j- 1] = ='. ') || (s[i- 1] == p[j- 1])) {
                dp[i][j] = dp[i- 1][j- 1];    // Match, same state as last time
            } else if ((j >= 2) && p[j- 1] = =The '*') {
                // * The number of characters to match is uncertain
                if (p[j2 -] = ='. ' || s[i- 1] == p[j2 -]) {
                    Dp [I][j] = dp[I][j] = dp[I][j-2]; Dp [I][j] = dp[I][j-1]; Dp [I][j] = dp[i-1][j-1] = dp[i-1] Dp [I][j] = dp[i-1][j] = dp[i-1][j] * /
                    dp[i][j] = dp[i][j2 -] || dp[i][j- 1] || dp[i- 1][j- 1] || dp[i- 1][j];
                } else {
                    dp[i][j] = dp[i][j2 -];    / / don't match}}else {
                dp[i][j] = 0; }}}return dp[sLen][pLen];  
}

/* int main(int argc, const char *argv[]) { char s[] = "aa"; char p[] = "a"; printf("%d\n", isMatch(s, p)); return 0; } * /
Copy the code