10. Regular Expression Matching

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;

// tree node stuff here...
#endif

static int __initialSetup = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}
();

// code using look-ahead logic -> life is a lot more easier
class Solution
{
private:
    string conv(int a, int b)
    {
        return to_string(a) + to_string(b);
    }

    unordered_map<string, bool> dp;
    bool match(string s, string p, int ps, int pp)
    {
        if (dp.find(conv(ps, pp)) != dp.end())
            return dp[conv(ps, pp)];

        if ((int)p.length() == pp) {        // no more pattern to match
            bool ret = (int)s.length() == ps; // empty string or not
            dp[conv(ps, pp)] = ret;
            return ret;
        }

        if ((int)s.length() == ps) { // run down the regex :)
            while (pp < (int)p.length()) {
                if (pp + 1 < (int)p.length() &&
                    p[pp + 1] == '*') // skip match all cases
                    pp += 2;
                else { // others: failing...
                    dp[conv(ps, pp)] = false;
                    return false;
                }
            }
            dp[conv(ps, pp)] = true;
            return true;
        }

        if (pp + 1 < (int)p.length() && p[pp + 1] == '*') { // a * term
            // match 0 or match 1+
            // case char or .
            bool ret =
                match(s, p, ps, pp + 2) ||
                (p[pp] == '.' ? match(s, p, ps + 1, pp)
                 : (p[pp] == s[ps] ? match(s, p, ps + 1, pp) : false));
            dp[conv(ps, pp)] = ret;
            return ret;
        } else { // a normal term
            // case char or .
            bool ret = p[pp] == '.'
                       ? match(s, p, ps + 1, pp + 1)
                       : (p[pp] == s[ps] ? match(s, p, ps + 1, pp + 1) : false);
            dp[conv(ps, pp)] = ret;
            return ret;
        }
    }

public:
    bool isMatch(string s, string p)
    {
        // return regex_match(s, regex(p));

        return match(s, p, 0, 0);
    }
};

// // code using look-ahead logic -> life is a lot more easier
// class Solution
// {
// private:
//     bool match(string s, string p, int ps, int pp)
//     {
//         if ((int)p.length() == pp) {    // no more pattern to match
//             return (int)s.length() == ps; // empty string or not
//         }

//         if ((int)s.length() == ps) { // run down the regex :)
//             while (pp < (int)p.length()) {
//                 if (pp + 1 < (int)p.length() && p[pp + 1] == '*')
//                     pp += 2;
//                 else
//                     return false;
//             }
//             return true;
//         }

//         if (pp + 1 < (int)p.length() && p[pp + 1] == '*') { // a * term
//             // match 0 or match 1+
//             // case char or .
//             return match(s, p, ps, pp + 2) ||
//                    (p[pp] == '.'
//                     ? match(s, p, ps + 1, pp)
//                     : (p[pp] == s[ps] ? match(s, p, ps + 1, pp) : false));
//         } else { // a normal term
//             // case char or .
//             return p[pp] == '.'
//                    ? match(s, p, ps + 1, pp + 1)
//                    : (p[pp] == s[ps] ? match(s, p, ps + 1, pp + 1) : false);
//         }
//     }

// public:
//     bool isMatch(string s, string p)
//     {
//         // return regex_match(s, regex(p));

//         return match(s, p, 0, 0);
//     }
// };

#ifdef LOCAL
int main()
{
    {
        string s = "";
        string p = "";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "aa";
        string p = "a*";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "cabc";
        string p = "c.*c";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "cab";
        string p = "c.*c";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "aab";
        string p = "c*a*b*";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "a";
        string p = "ab*";
        cout << Solution().isMatch(s, p) << endl;
    }
    return 0;
}
#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;

// tree node stuff here...
#endif

static int __initialSetup = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}
();

class Solution
{
public:
    bool isMatch(string s, string p)
    {
        int n = s.length(), m = p.length();
        bool dp[n + 1][m + 1];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) // init column 0
            dp[i][0] = false;
        for (int i = 2; i <= m; i++) // init row 0
            if (p[i - 1] == '*')
                // only deal with * case
                dp[0][i] = dp[0][i - 1] || dp[0][i - 2];

        for (int i = 1; i <= n; i++) { // for every possible prefix of input string
            for (int j = 1; j <= m; j++) { // run the regex against it
                if (p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    if (dp[i][j - 1]) // match 1
                        dp[i][j] = true;
                    else if (dp[i][j - 2]) // match 0
                        dp[i][j] = true;
                    else if (dp[i - 1][j] &&
                             ((s[i - 1] == p[j - 2]) || p[j - 2] == '.')) // match many
                        // aa match a*
                        // we look if a matches a* and a == a!
                        dp[i][j] = true;
                } else {
                    // single character match
                    // aaaa match a*
                    // at i = 2 j = 1, aa match a is a false
                    // since a match {} is false, by appending a to both sides won't get
                    // an true
                    dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
                }
            }
        }

        /*
        for (int i = 0; i <= n; i++) {
            printf("%c ", i == 0 ? ' ' : s[i - 1]);
            if (i == 0)
                for (int j = 0; j <= m; j++)
                    printf("%c%c", j == 0 ? ' ' : p[j - 1], j == m ? '\n' : ' ');

            if (i == 0)
                printf("  ");
            for (int j = 0; j <= m; j++) {
                printf("%d%c", dp[i][j] == true ? 1 : 0, j == m ? '\n' : ' ');
            }
        }
        */
        return dp[n][m];
    }
};

#ifdef LOCAL
int main()
{
    {
        string s = "aaaa";
        string p = "a*";
        cout << Solution().isMatch(s, p) << endl;
    }
    {
        string s = "aaba";
        string p = "ab*a*c*a";
        cout << Solution().isMatch(s, p) << endl;
    }

    return 0;
}
#endif