10. Regular Expression Matching

Let's make this one less mysterious. For 10. Regular Expression Matching, the solution in this repository is mainly a DFS + memoization solution.

Guide

What?

We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:

What state are we keeping?
How do we move from one state to the next?
When do we know the answer is already determined?

For this file, the main tools are: DFS + memoization, dynamic programming.

The notes already sitting in the source point us in the right direction:

recursion
https://github.com/keineahnung2345/fucking-algorithm/blob/note/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE.md
time: O((T+P)*2^(T+P/2))?
space: O(T^2+P^2)?

Guide

When?

This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.

The important function names to track are isMatch, dfs.

Guide

Why?

The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.

The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Substring checks are convenient but not free, so they are part of the real complexity story.
The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.

Guide

How?

Walk through the solution in this order:

Initialize the memory or helper structure.
Process candidates in the order the invariant expects.
Update the answer only when the current state is valid.
Return the value that represents the fully processed input.

The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.

Guide

Complexity

Time: O((T+P)*2^(T+P/2))?
Space: O(T^2+P^2)?

Guide

C++ Solution

Your submission

The accepted solution

solution.cpp

01//recursion
02//https://github.com/keineahnung2345/fucking-algorithm/blob/note/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE.md
03//Runtime: 616 ms, faster than 8.19% of C++ online submissions for Regular Expression Matching.
04//Memory Usage: 13.5 MB, less than 11.87% of C++ online submissions for Regular Expression Matching.
05//time: O((T+P)*2^(T+P/2))?
06//space: O(T^2+P^2)?
07class Solution {
08public:
09    bool isMatch(string s, string p) {
10        if(p.size() == 0) return s.size() == 0;
11        
12        // cout << p << " " << s << endl;
13        
14        //edge case
15        if(s.size() == 0){
16            // return p.size() == 2 && p[1] == '*';
17            //c*c*
18            //when s is empty, p can match s only it's a combination of "?*"
19            if(p.size() % 2 != 0) return false;
20            for(int i = 1; i < p.size(); i+=2){
21                if(p[i] != '*') return false;
22            }
23            return true;
24        }
25        
26        //here s and p are both not empty
27        
28        bool first_match = (p[0] == '.' || p[0] == s[0]);
29        
30        if(p.size() >= 2 && p[1] == '*'){
31            /*
32            discover '*'
33            either match the first 2 char of s or not match
34            (ignore the first 2 char of p)
35            
36            for the first case: 1st char must match, so there is a "first_match"
37            for the second case: ignore the x* in p
38            */
39            return (first_match && isMatch(s.substr(1), p)) ||
40                isMatch(s, p.substr(2));
41        }else{
42            /*
43            when discovering '*', we must consider the first 2 char of p together,
44            so we should not go here
45            */
46            return first_match && isMatch(s.substr(1), p.substr(1));
47        }
48    }
49};
50
51//recursion, no edge case
52//Runtime: 596 ms, faster than 12.34% of C++ online submissions for Regular Expression Matching.
53//Memory Usage: 13.6 MB, less than 11.87% of C++ online submissions for Regular Expression Matching.
54class Solution {
55public:
56    bool isMatch(string s, string p) {
57        if(p.size() == 0) return s.size() == 0;
58        
59        // cout << p << " " << s << endl;
60        
61        // //edge case
62        // if(s.size() == 0){
63        //     // return p.size() == 2 && p[1] == '*';
64        //     //c*c*
65        //     //when s is empty, p can match s only it's a combination of "?*"
66        //     if(p.size() % 2 != 0) return false;
67        //     for(int i = 1; i < p.size(); i+=2){
68        //         if(p[i] != '*') return false;
69        //     }
70        //     return true;
71        // }
72        
73        //here s and p are both not empty
74        
75        //we should check whether s is not empty!
76        //so we don't need the handle of edge case above
77        bool first_match = (s.size() > 0) && (p[0] == '.' || p[0] == s[0]);
78        
79        if(p.size() >= 2 && p[1] == '*'){
80            /*
81            discover '*'
82            either match the first 2 char of s or not match
83            (ignore the first 2 char of p)
84            
85            for the first case: 1st char must match, so there is a "first_match"
86            for the second case: ignore the x* in p
87            */
88            return (first_match && isMatch(s.substr(1), p)) ||
89                isMatch(s, p.substr(2));
90        }else{
91            /*
92            when discovering '*', we must consider the first 2 char of p together,
93            so we should not go here
94            */
95            return first_match && isMatch(s.substr(1), p.substr(1));
96        }
97    }
98};
99
100//recursion + memorization
101//https://github.com/keineahnung2345/fucking-algorithm/blob/note/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE.md
102//Runtime: 4 ms, faster than 95.00% of C++ online submissions for Regular Expression Matching.
103//Memory Usage: 7 MB, less than 100.00% of C++ online submissions for Regular Expression Matching.
104class Solution {
105public:
106    string s, p;
107    vector<vector<int>> memo;
108    
109    bool dfs(int i, int j){
110        //i for s, j for p
111        if(j == p.size()) return i == s.size();
112        
113        if(memo[i][j] != -1){
114            return memo[i][j];
115        }
116        
117        // cout << i << " " << j << endl;
118        
119        //edge case
120        if(i == s.size()){
121            //(p.size()-j): remaining size
122            if((p.size()-j) % 2 != 0) return false;
123            for(int k = j+1; k < p.size(); k+=2){
124                if(p[k] != '*') return false;
125            }
126            return true;
127        }
128        
129        bool first_match = (p[j] == '.' || p[j] == s[i]);
130        
131        if(j+1 < p.size() && p[j+1] == '*'){
132            memo[i][j] = (first_match && dfs(i+1, j)) ||
133                dfs(i, j+2);
134        }else{
135            memo[i][j] =  first_match && dfs(i+1, j+1);
136        }
137        
138        return memo[i][j];
139    }
140    
141    bool isMatch(string s, string p) {
142        this->s = s;
143        this->p = p;
144        memo = vector<vector<int>>(s.size()+1, vector(p.size()+1, -1));
145        return dfs(0, 0);
146    }
147};
148
149//recursion + memorization, no edge case
150//Runtime: 4 ms, faster than 95.05% of C++ online submissions for Regular Expression Matching.
151//Memory Usage: 7 MB, less than 100.00% of C++ online submissions for Regular Expression Matching.
152class Solution {
153public:
154    string s, p;
155    vector<vector<int>> memo;
156    
157    bool dfs(int i, int j){
158        //i for s, j for p
159        if(j == p.size()) return i == s.size();
160        
161        if(memo[i][j] != -1){
162            return memo[i][j];
163        }
164        
165        // cout << i << " " << j << endl;
166        
167        bool first_match = (i < s.size()) && (p[j] == '.' || p[j] == s[i]);
168        
169        if(j+1 < p.size() && p[j+1] == '*'){
170            memo[i][j] = (first_match && dfs(i+1, j)) ||
171                dfs(i, j+2);
172        }else{
173            memo[i][j] =  first_match && dfs(i+1, j+1);
174        }
175        
176        return memo[i][j];
177    }
178    
179    bool isMatch(string s, string p) {
180        this->s = s;
181        this->p = p;
182        memo = vector<vector<int>>(s.size()+1, vector(p.size()+1, -1));
183        return dfs(0, 0);
184    }
185};
186
187//DP, bottom-up
188//Runtime: 12 ms, faster than 54.45% of C++ online submissions for Regular Expression Matching.
189//Memory Usage: 6.6 MB, less than 100.00% of C++ online submissions for Regular Expression Matching.
190//time: O(mn), space: O(mn)
191class Solution {
192public:
193    bool isMatch(string s, string p) {
194        int m = s.size(), n = p.size();
195        //dp[i,j] : substring starts from (i, j)
196        //i 's range: [0, m], 0 means the whole string, m means empty string
197        vector<vector<bool>> dp(m+1, vector(n+1, false));
198        
199        //base case when both are empty string
200        dp[m][n] = true;
201        /*
202        dp[i][n] means when i is not equal to m:
203        that means s is not empty, but p is empty,
204        that's always false
205        */
206        
207        for(int i = m; i >= 0; i--){
208            //dp[i][n] are already set
209            for(int j = n-1; j >= 0; j--){
210                // cout << "(" << i << ", " << j << ")" << endl;
211                bool first_match = (i < m) && (p[j] == '.' || p[j] == s[i]);
212                
213                if(j+1 < n && p[j+1] == '*'){
214                    //match first char or ignore "?*" in p
215                    dp[i][j] = (first_match && dp[i+1][j]) || dp[i][j+2];
216                }else{
217                    dp[i][j] = first_match && dp[i+1][j+1];
218                }
219            }
220        }
221        
222        //whole string of s and whole string of p
223        return dp[0][0];
224    }
225};

Cost

Complexity

Time

O((T+P)*2^(T+P/2))?

Dominated by the main traversal, recursion, or data-structure operations in the code.

Space

O(T^2+P^2)?

Auxiliary state plus the answer structure where the problem requires one.