【記憶化搜尋】LeetCode 10. 正規表達式比對

這段時間要沉迷刷題一段時間了，就讓CSDN陪我一起吧！

一、題目大意

題目要求很簡單，就是給定一個比對串s，和一個模式串p，要求按照正規表達式的要求進行比對，支援’.‘和’*'的比對。

二、題目思路以及AC代碼

我本來是抵制LeetCode的題的，在這裡我不得不吐槽一下LeetCode的送出方式，簡直是太智障了！！(我是被同學提問說要做這道題的，本身并不情願)，為什麼就不能像其他OJ那樣送出呢?偏自己搞一個Solution送出，把本來優化的時間複雜度都能再提上去，真的服。

回歸正題，本題要求比對正規表達式。其實思路很簡單，就是按照比對規則遞歸求解嘛，當然這是暴力的方法，然後優化的方法自然想到的就是記憶化搜尋，用一個dp數組存儲一下已經算出來的值。

下面給出AC代碼：(提前聲明，我的代碼并沒有完全按照LeetCode上的寫法，因為我定義了全局變量，但大家可以參照我寫的思路來解決，其中的match函數我用了記憶化搜尋，結果導緻時間用的更多了，我嚴重懷疑是因為我改到LeetCode上的時候采用了成員變量，用指針而導緻時間花費的提高，代碼本身并沒有問題)

純暴力

bool isMatch(string s, string p) {
	int plen = p.length();
	int slen = s.length();

	if (!plen) return slen == 0;

	char a = s[0];
	char b = p[0];

	bool first_match = slen && (a == b || b == '.');

	if (plen >= 2 && p[1] == '*') {
		return isMatch(s, p.substr(2, plen - 2)) ||
			first_match && isMatch(s.substr(1, slen - 1), p);
	}
	else {
		return first_match && isMatch(s.substr(1, slen - 1), p.substr(1, plen - 1));
	}
}
           

記憶化搜尋：

bool match(int i, int j) {
	if (j >= plen) return i >= slen;

	char a = s[i];
	char b = p[j];

	bool first_match = i < slen && (a == b || b == '.');

	if (plen - j >= 2 && p[j + 1] == '*') {
		dp[i][j + 2] = (dp[i][j + 2] == -1) ? match(i, j + 2) : dp[i][j + 2];
		bool tmp = (first_match && ((dp[i + 1][j] == -1) ? (dp[i + 1][j] = match(i + 1, j)) : dp[i + 1][j]));
		return dp[i][j + 2] || tmp;
	}
	else {
		return (first_match && ((dp[i + 1][j + 1] == -1) ? (dp[i + 1][j + 1] = match(i + 1, j + 1)) : dp[i + 1][j + 1]));
	}
}
           

哎，簡單的一道題在LeetCode上費那麼多時間！我保證這是我最後一次在這個平台上刷題！

如果有問題的話，請大家指正！！！