[LeetCode] 010. Regular Expression Matching (Hard) (C++/Java

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

010.Regular_Expression_Matching(Hard) 链接：

题目：https://oj.leetcode.com/problems/regular-expression-matching/代码(github)：https://github.com/illuz/leetcode

题意：

给一个原串和一个正则表达式，问能不能匹配。

分析：偷懒的方法是直接用语言自带的正则实现。(Python 又是一句话 =w=)用 DFS 的方法可以用 DP 的方法用数组 DP :dp[i][j] 表示 s[0..i] 和 p[0..j] 是否 match，当 p[j] != ‘*’，b[i + 1][j + 1] = b[i][j] && s[i] == p[j] ，当p[j] == ‘*’ 要再分类讨论，具体可以参考DP C++，，还可以压缩下把 dp 降成一维：参考这里用记忆化，就是把算过的结果保存下来，下次就不用再算了代码：

C++: (DFS)

class Solution {public:bool isMatch(const char *s, const char *p) {if (!p[0])return !s[0];int slen = strlen(s), plen = strlen(p);if (plen == 1 || p[1] != '*')return slen && (p[0] == '.' || s[0] == p[0])&& isMatch(s + 1, p + 1);while (s[0] && (p[0] == '.' || s[0] == p[0]))if (isMatch(s++, p + 2))return true;return isMatch(s, p + 2);}};

Java: (数组 DP)

public class Solution {public boolean isMatch(String s, String p) {int lens = s.length();int lenp = p.length();if (lens == 0 && lenp == 0)return true;// initboolean[][] dp = new boolean[2][lenp + 1];dp[0][0] = dp[1][0] = true;for (int j = 2; j <= lenp; ++j) {if (p.charAt(j – 1) == '*' && dp[0][j – 2]) {dp[0][j] = dp[1][j] = true;}}// dpfor (int i = 1; i <= lens; ++i) {dp[i&1][0] = false;for (int j = 1; j <= lenp; ++j) {dp[i&1][j] = ((p.charAt(j – 1) == s.charAt(i – 1) || p.charAt(j – 1) == '.') && dp[1-(i&1)][j – 1])|| p.charAt(j – 1) == '*' && (p.charAt(j – 2) == s.charAt(i – 1) || p.charAt(j – 2) == '.') && dp[1-(i&1)][j]|| (j >= 2 && p.charAt(j – 1) == '*' && dp[i&1][j – 2]);}}return dp[lens&1][lenp];}}

Python: (记忆化 DP)

class Solution:cache = {}# @return a booleandef isMatch(self, s, p):if (s, p) in self.cache:return self.cache[(s, p)]if not p:return not sif len(p) == 1 or p[1] != '*':self.cache[(s[1:], p[1:])] = self.isMatch(s[1:], p[1:])return len(s) > 0 and (p[0] == '.' or s[0] == p[0]) \and self.cache[(s[1:], p[1:])]while s and (p[0] == '.' or s[0] == p[0]):self.cache[(s, p[2:])] = self.isMatch(s, p[2:])if self.cache[(s, p[2:])]:return Trues = s[1:]self.cache[(s, p[2:])] = self.isMatch(s, p[2:])return self.cache[(s, p[2:])]

Python: (用 regex)

class Solution:# @return a booleandef isMatch(self, s, p):return re.match('^' + p + '$', s) != None

最重要的是今天的心。