Implement regular expression matching with support for ‘.’ and ‘*’.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
'.' 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
|
解法1： DP O(MN)
这题一开始拿到没想到可以用DP。如果从基础的递归开始思考的话会比较容易一点往dp的方向上想。
而dp的状态方程也不太好想。
参考了YouTube上的这个视频,讲的还是比较清楚的。
首先，dp[i][j]表示的是前i个字符和前j个字符是否能match。
那么如果s[i] == p[j]，又或者当前的pattern是”.”, 则可以轻松得出dp[i][j] = dp[i - 1][j - 1]
如果是,那么就稍微麻烦一点。
这里可以考虑的是两种情况：
一个是不match前面的字符，这种情况下可以得到dp[i][j] = dp[i][j - 2]
另外一个是match一个或者多个前面的字符，但是这种情况需要满足s[i] = p[j - 1].
那么怎么表示match呢？可以的做法就是把当前s的位置的字符删除，变成s[i - 1]再和p[i]尝试match.
举一个例子：aa 和a*。 如果在match第二个a的时候，可以退化成比较a和a*。而这个结果已经有了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
class { public boolean isMatch(String s, String p) { if (s == null && p == null) return true; if (s == null || p == null) return false; if (s.length() == 0 && p.length() == 0) return true; int m = s.length(); int n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int i = 2; i <= n; i++) { if (p.charAt(i - 1) == '*') { dp[0][i] = dp[0][i - 2]; } } for (int i = 1; i <=m ; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j - 1) == '.' || (p.charAt(j - 1) == s.charAt(i - 1))) { dp[i][j] = dp[i - 1][j - 1]; } else if (p.charAt(j - 1) == '*') { dp[i][j] = dp[i][j - 2]; if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) { dp[i][j] |= dp[i - 1][j]; } } else { dp[i][j] = false; } } } return dp[m][n]; } }
|
近期评论