---
tags: LeetCode,Top 100 Liked Questions
---
# 10. Regular Expression Matching
https://leetcode.com/problems/regular-expression-matching/
## 題目敘述
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
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

## 解題想法
### 1. Recursion
a\*b 可表示成 aaab 或 b
所以先檢查p[1]==*
經過以下流程後有幾種邊界條件
(1)s和p皆比對完 ==> true
(2)p剩一個 且為"." or 和 s[0] 相同 => true
(3)p剩多於一個 且s沒有 ==> false

%%{init: {
        'theme': 'neutral', 
        "flowchart" : { "curve" : "basis" } 
    } }%%
graph LR
    Start --> B{"p[1]==*"}
    B -->|yes| C{"p[0]==s[0]"}
    C -->|yes| E{"在s找到最後一個連續的p[0]"}
    C -->|no| F{"從p[2]開始繼續比對<br>"}
    B -->|no| D{s還有沒有}
    D -->|yes| h{"if s[0]==p[0] or p[0]=='.'<br>往後檢查"}
    D -->|no| g[false]

bool isMatch(string s, string p)
{
    if (p.empty()) 
    {
        return s.empty();
    }
    if (p.length() == 1)
    {
        return (s.length() == 1 && (p[0] == s[0] || p[0] == '.'));
    }
    if (p[1] != '*')
    {
        if (s.empty())
        {
            return false;
        }
        return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        //s[0]==p[0] or p[0]=. 往後檢查
    }
    while (!s.empty() && (s[0] == p[0] || p[0] == '.'))
    {
        if (isMatch(s, p.substr(2)))
        {
            return true;
        }
        s = s.substr(1);//s去掉和p比對成功的
    }
    return isMatch(s, p.substr(2));//讓p去掉 "字母*"後繼續比對
}

### 2. DP