【LeetCode #10 題解】 正則表達式匹配

一、題目

給你一個字串 s 和一個字元規律 p，請你來實現一個支援 ‘.’ 和 ‘*’ 的正則表達式匹配。

'.' 匹配任意單個字元
'*' 匹配零個或多個前面的那一個元素

所謂匹配，是要涵蓋 整個 字串 s的，而不是部分字串。

說明:

• s 可能爲空，且只包含從 a-z 的小寫字母。
• p 可能爲空，且只包含從 a-z 的小寫字母，以及字元 . 和 *。

• 範例 1

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字串。

• 範例 2

輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因爲 '*' 代表可以匹配零個或多個前面的那一個元素, 在這裏前面的元素就是 'a'。因此，字串 "aa" 可被視爲 'a' 重複了一次。

• 範例 3

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字元（'.'）。

• 範例 4

輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因爲 '*' 表示零個或多個，這裏 'c' 爲 0 個, 'a' 被重複一次。因此可以匹配字串 "aab"。

• 範例 5

輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false

二、C語言題解

題解思路採用的是遞回的方法：

1. p 爲空字串的情況
   如果 p 爲空 且 s 爲空，返回true 匹配； 否則不匹配

2. p 非空時
   (1) 判斷首字母是否匹配，如果 s 非空 且 *s ==*p 或 *p=='.'
   如果 s 爲空，則首字母匹配失敗，直接返回false 不匹配

   (2) 判斷 * 的情況，分爲匹配0 個和 匹配1個的情況
   匹配 0 個時，直接 p = p+2 ，繼續匹配下一個
   匹配多個時，直接 s = s+1， p 保持不變，遞回呼叫匹配下一個

   (3) 非. 也 非 * 時，單個字元愛漸匹配， ++s， ++p

遞回退出條件是，單個字元匹配 直到 s 爲空 或者 p 爲空

程式碼實現如下：

bool isMatch(char * s, char * p){

    // p 爲空字串時, s 爲空匹配，s 非空不匹配
    if( p != NULL && strlen(p)==0 )
        return s != NULL && strlen(s)==0 ? true : false;

    // 首字元是否匹配，用於判斷 * 的情況  ，
    // 例如 a*  , 如果首字母不匹配，就是下匹配0個，如果首字母匹配，則可能匹配N 個
    bool first_match = *s && (*s==*p || *p=='.');
    
    // 如果 p+1 == '*' , 匹配 0 個字元， 或者 遞回匹配1 個字元，直到匹配0 個字元結束
    if( *(p+1) == '*' ){
        return isMatch(s, p+2) || (first_match && isMatch(++s, p));
    } 
    else
    {
        // 單個字元逐漸匹配
        return first_match && isMatch(++s, ++p);
    }
}