👉 “Offer to drive, dig friends to accept! I am participating in the 2022 Spring Recruit Punch card activity click to see the details of the activity.

19. Regular expression matching

Implement a function to match regular expressions containing ‘. ‘and ”. The character ‘.’ in the pattern represents any character, and the character ” indicates that the character preceding it can occur any number of times (up to zero). In this case, matching means that all characters in a string match the entire pattern. For example, the string “aaa” matches the patterns “A.a” and “abaca”, but not “aa.a” and “ab*a”.

Example 1:

Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa".Copy the code

Example 2:

Input: s = "aa" p = "a*" Output: true Thus, the string "aa" can be treated as 'a' repeated once.Copy the code

Example 3:

Input: s = "ab" p = ". * "output: true explanation:" * "said can match zero or more (' * ') any character ('. ').Copy the code

Example 4:

Input: s = "aab" p = "c*a*b" Output: true Explanation: Since '*' means zero or more, where 'c' is zero, 'a' is repeated once. So it matches the string "aab".Copy the code

Example 5:

Input: s = "Mississippi" p = "mis*is*p*." output: falseCopy the code

Description:

S may be empty and contain only lowercase letters from A to Z. P may be empty and contains only lowercase letters from a to Z and the characters. And *, without consecutive '*'.Copy the code
Idea: Dynamic planning

  • State definition:f[i][j]saidsString toiSubstring at the end,pIn the tojWhether the trailing substring matches.

  • The final result returned is:f[m][n]

  • State transition:

    • ifp[j]Is a common characterf[i][j] = f[i - 1][j - 1] && s[i] == p[j].
    • ifp[j]for'. 'At this time,F [I][j] = F [i-1][J-1] &&p [J] == '..
    • ifp[j]forThe '*'At this time due toThe '*'Can not be used alone, need to be combined with the character before it, so need to look atp[j - 1]The character and then lookx*withsThe number of matches in the string is 0, 1, 2…
      • Match 0:f[i][j] = f[i][j - 2]
      • If I match one,f[i][j] = f[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')
      • Match 2 of them,f[i][j] = f[i - 2][j - 2] && ( ( s[i] == p[j - 1] && s[i - 1] == p[j - 1] ) || p[j] == '.' )
      • …

  • To sum up:

    f[i][j] = f[i][j - 2] || (f[i - 1][j - 2] && s[i] == p[j - 1]) || (f[i - 2][j - 2] && s[i] == p[j - 1] && s[i - 1] == p[j - 1]) ||......

    If I = i-1 is substituted into the above formula, it can be obtained:

    f[i - 1][j] = f[i - 1][j - 2] || f[i - 2][j - 2] && s[i - 1] == p[j - 1] || f[i - 3][j - 2] && s[i - 1] == p[j - 1] && s[i - 2] == p[j - 1]) || ......

  • By comparing the above two formulas, it can be obtained:

    f[i][j] = f[i][j - 2] || f[i - 1][j] && s[i] == p[j - 1]

  • Therefore:

    f[i][j] = f[i][j - 2] || (f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'))

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size(a); vector<vector<bool>> f(m + 1,vector<bool>(n + 1.false));
        s.insert(s.begin(),' ');
        p.insert(p.begin(),' ');
        f[0] [0] = true;
        // Handle f[0][j]
        for(int j = 1; j <= n; j++){
            if(p[j] == The '*') f[0][j] = f[0][j - 1];
            else if(j + 1 > n or p[j + 1] != The '*') break;
            else f[0][j] = true;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(j + 1 <= n and p[j + 1] = =The '*') continue;
                if(p[j] ! =The '*') f[i][j] = f[i - 1][j - 1] and ( s[i] == p[j] or p[j] == '. ' );
                else if(p[j] == The '*') {
                    f[i][j] = (j >= 2 and f[i][j - 2]) or f[i - 1][j] and (s[i] == p[j - 1] or p[j - 1] = ='. '); }}}returnf[m][n]; }};Copy the code