Leetcode 10: Regular Expression Matching

本文主要是介绍Leetcode 10: Regular Expression Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 10: Regular Expression Matching

Implement regular expression matching with support for ‘.’ 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

分析

其实我老是会忘正则表达式里的一些概念
比如 * 是指与前一个字符的匹配情况： 0 1 2 3 … 个

还是 dp，这里确实是涉及子问题的。

dp[i][j] : s[0…i-1] 与 p[0…j-1]的匹配情况，true or false

如何求解dp呢？

dp[i][j] : s[0…i-1] p[0…j-1] ，讨论 p[j-1]
若 p[j-1] 为 *
则是关于 p[j-2] 匹配 0/1/多个的情况了
匹配0个： s[0…i-1] p[0…j-3]
dp[i][j] = dp[i][j-2]
匹配1个： s[0…i-1] p[0…j-2]
dp[i][j] = dp[i][j-1] 
匹配多个： s[0…i-2] p[0…j-1]
 dp[i][j] = dp[i-1][j-1] && (p[j-2] == s[i-1] || p[j-2] == '.')
若p[j-1] 不为 *
dp[i][j] = dp[i-1][j-1] && (p[j-1]==s[i-1] || p[j-1]=='.')
dp的初始化也值得探讨一下：
int[][] dp = new int[length][length];
dp[0][0] = true;
//dp[0][j], 考虑p形如  x* 格式的字符串，需要想一想
for(int j=1; j<=p.length(); j++){if(p.charAt(j-1)=='*' && dp[0][j-2]){dp[0][j] = true; }
}

解答

public class Solution {public boolean isMatch(String s, String p) {return isMatchByDP(s,p);        }/*** dp[i][j] saves the s[0:i-1] and p[0:j-1] match result.*/ public boolean isMatchByDP(String s, String p){boolean[][] dp = new boolean[s.length()+1][p.length()+1];dp[0][0]=true;// init dp[0][j], null character match x*, only match zero.for(int j=1; j<=p.length(); j++){if(p.charAt(j-1)=='*' && dp[0][j-2]){dp[0][j] = true; }}for(int i=1; i<=s.length();i++){for(int j=1; j<=p.length();j++){if(p.charAt(j-1)!='*'){dp[i][j]= dp[i-1][j-1] &&(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.');}else{ // p[j-1]=='*'//match one p[j-2]match zero p[j-2]if(dp[i][j-1] || dp[i][j-2] || (dp[i-1][j] && (s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.'))){dp[i][j]=true;}else {dp[i][j]=false;}}}}return dp[s.length()][p.length()];}}