LeetCode 10. Regular Expression Matching ( C )-Hard

題目為給定兩個字串，第二個字串為字串格式，比對兩字串是否相符。

‘ . ‘ 代表任意單一字元 ， ‘ * ‘ 代表前一字元可以為0次出現或任意次數出現。

題目原文如下

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where: 

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

 

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
 

Constraints:

0 <= s.length <= 20
0 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

解題方法為採用遞迴策略，如程式碼所示。

下面是我的程式碼

bool isMatch(char * s, char * p){
    if(strlen(s) == 0 && strlen(p) == 0){
        return true;
    }
    
    if(strlen(p) > 1 && p[1] == '*'){
        if(isMatch(s,&p[2])){
            return true;
        }
        if((p[0] == '.' || s[0] == p[0]) && strlen(s) > 0){
            return isMatch(&s[1],p);
        }
        return false;
    }
    else{
        if((p[0] == '.' || p[0] == s[0]) && strlen(s) > 0){
            return isMatch(&s[1],&p[1]);
        }
        return false;
    }
    return false;
}

下面是時間與空間之消耗

Runtime: 40 ms, faster than 20.23 % of C online submissions for Regular Expression Matching.

Memory Usage: 5.5 MB, less than 78.61 % of C online submissions for Regular Expression Matching.

本題官方解答還有採用動態規劃，可以到 LeetCode上查詢。

下一題連結 : LeetCode 11. Container With Most Water ( C )-Medium