Problem description:

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

Solution:

create dp array. dp[i][j] to be true if s[0..i) matches p[0..j)

  1. If p[j] == s[i] : dp[i][j] = dp[i-1][j-1];
    If the character on position j in string p is equal to the character on position i in string s.

  2. If p[j] == ‘.’ : dp[i][j] = dp[i-1][j-1];
    If the character on position j in string p is a ‘.’, it can match any character, so dp[i][j] follow dp[i-1][j-1].

  3. If p[j] == ‘*’:
    there are two sub conditions:

    1. if p[j-1] != s[i] : dp[i][j] = dp[i][j-2] //in this case, $a*$ only counts as empty
    2. if p[j-1] == s[i] or p[j-1] == ‘.’:
      dp[i][j] = dp[i-1][j] //in this case, $a*$ counts as multiple a
      or dp[i][j] = dp[i][j-1] // in this case, $a*$ counts as single a
      or dp[i][j] = dp[i][j-2] // in this case, $a*$ counts as empty
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
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        if not s and not p:
             return True
        dp = [[False for _ in range(n+1)] for _ in range(m+1)]
        dp[0][0] = True
        
        for j in range(n):
            if p[j] == '*' and dp[0][j-1]:
                dp[0][j+1] = True
        
        for i in range(m):
            for j in range(n):
                if s[i] == p[j]:
                    dp[i+1][j+1] = dp[i][j]
                if p[j] == '.': # this character doesn't matter, check if it's true until now
                    dp[i+1][j+1] = dp[i][j] 
                if p[j] == '*':
                    # two cases: 
                    # 1. character before * not the same
                    # bc* vs b, in this case, c* could count as empty, so we check dp[i][j-1]
                    # 2. character before * is the same or '.'
                    if p[j-1] != '.' and s[i] != p[j-1]:
                        dp[i+1][j+1] = dp[i+1][j-1]
                    else:
                        dp[i+1][j+1] = dp[i+1][j] or dp[i][j+1] or dp[i+1][j-1]
        return dp[m][n]
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
class Solution {
public:
    bool isMatch(string s, string p) {
        /*
        create dp array. dp[i][j] to be true if s[0..i) matches p[0..j)
        1. edge case
        2. dp array init
        3. 
        */
        //edge case, both NULL
        if(s.empty() && p.empty()) return true;
        int r= s.length(), c= p.length();
        vector<vector<bool>> dp(r+1, vector<bool>(c+1, false));
        dp[0][0]= true; //both empty is true
        for(int j= 0; j< c; j++){
            if(p[j] == '*' && dp[0][j-1]) //previous is the same, current is '*'
                dp[0][j+1]= true;
        }
        
        for(int i= 0; i< r; i++){
            for(int j= 0; j< c; j++){
                if(s[i]== p[j]) dp[i+1][j+1]= dp[i][j];
                if(p[j]== '.') dp[i+1][j+1]= dp[i][j]; //ex: abc, ab.
                if(p[j]== '*'){
                    if(p[j-1] != '.' && p[j-1] != s[i]) //can not use special character to represent any word
                        dp[i+1][j+1]= dp[i+1][j-1]; //the same as 
                    else
                        dp[i+1][j+1]= (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
        return dp[r][c];
    }
};

time complexity: $O(mn)$
space complexity: $O(mn)$
reference:
https://goo.gl/1yJRGK
https://goo.gl/sFR26t