10. Regular Expression Matching(hard)

這可能是刷過的最難的一題了

題目的要求是實現正則表達式. and *的功能

. Matches any single character.

* Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

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

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

我還沒學過正則表達式，不理解實現的原理，拿到這題是很蒙的

.還好，*是真的難辦，因為根本不知道會匹配多長的子串

舉個例子

「aaa」

「a*aab*」

*唯一的限制是match preceding element,那對於這種情況第一個*可以匹配一個a，也可以匹配兩個a,丟棄後面一個a，或者直接匹配0個字元也可以，如果只是簡單地以這樣一個例子來分析，似乎可以從簡處理，但是從一個很長的字元串的角度來考慮，當前面一個*的處理辦法被選定，後面一個*如果匹配失敗就得回溯重新選擇。

也就是說，每一個*需要把所有可能的情況都試一遍，示例代碼：

class Solution {public: static const int FRONT=-1; bool isMatch(string s, string p) { return myMatch(s,s.length()-1,p,p.length()-1); } bool myMatch(string s, int i, string p,int j) { if(j == FRONT) if(i == FRONT) return true; else return false; if(p[j] == *) { if(i > FRONT && (p[j-1] == . || p[j-1] == s[i])) if(myMatch(s,i-1,p,j)) return true; return myMatch(s,i,p,j-2); } if(p[j] == . || p[j] == s[i]) return myMatch(s,i-1,p,j-1); return false; }};

這段代碼是我從Vosky的csdn博客摘錄的，相比我自己的有兩個優點：

1.從後往前相比從前往後，省去了記錄上一個索引的內容的工作

2.if(i > FRONT && (p[j-1] == . || p[j-1] == s[i]))

我在寫的時候，這部分是循環實現的，相比之下這個遞歸更簡潔精鍊

初次閱讀的時候這個遞歸我沒有看懂，它的精髓之處這一段會再次執行，每次i--嘗試完匹配N個字元的情況，頗有種「自動遞歸」的感覺

或者可以使用DP，效率比遞歸可以提高60%,邏輯是一樣的。