leecode剑指 Offer 19. 正则表达式匹配
原创leecode剑指 Offer 19. 正则表达式匹配
原创
【动态规划】
动态规划能够通过空间换时间，就是将一个问题转移成，子问题。子问题会存储在线性表里面。
动态规划的重点式如何将一个问题变为无数个子问题。这个过程中用到的方法就是状态转移方程。在写代码的时候注意初始条件也很重要。
【动态规划分析】
（1） s=null，P=null，结果为正确
（2） s=a, p=a， 结果为true
（3） s=ab, p=ab，结果为true
（4） s=ab, p=ab*，结果为true
（5） s=abb, p=ab*，结果为true
（6） s=abbb, p=ab* 结果为true
以上的分析（1）就是（2）的子问题。（2）式3的子问题… (7)是（8）的子问题。
如上可以分析出对于s=abbbb, p=ab*，就有了状态转移方程。
(1) 当p中无*的时候，如(1),(2),(3)从p中，和s中各取一个字符。如果相等那么
定义f[x][y]=f[x-1][y-1]
(2) 如果p中取的值为*，如(4),(5)(6)。那么对于（4）
如果s[i]=p[j]，那么
f[x][y]=f[x][y-1]. 既是转移成(3)
(3) 对于(5)
f[x][y]=f[x-1][y]
(4) 对于（6）
f[x][y]=f[x-1][y]
另一种场景，s=a, p=ab*那么，
f[x][y]=f[x][y-2]
从而得到状态转移方程
f[x][y]=f[x-1][y-1] （当s[i]==p[j],p[j]!=* ）
f[x][y]=f[x-1][y]||f[x][y-2]||f[x][y-1](当p[j]==*,且s[i]=p[j-1])
【总结后代码如下】
上面分析的是总体思路，里面细节还有很多。
public static boolean isMatch(String s, String p) {
int sLength = s.length();
int pLength = p.length();
System.out.println(s.length());
boolean dp[][] = new boolean[sLength+1][pLength+1];
dp[0][0]=true;//代表f[0][0]
for(int i=0;i<=sLength;i++){
for(int j=1;j<=pLength;j++){
if(p.charAt(j-1) == '*'){
//如果s为空，p为x*那么就不会遍历到
dp[i][j]=dp[i][j-2];
//
if(checkMath(s,p,i,j-1)){
dp[i][j]||=(dp[i-1][j]||dp[i][j-1]);
}
}
else{
if(checkMath(s,p,i,j)){
dp[i][j]=dp[i-1][j-1];
};
}
}
}
return dp[sLength][pLength];
}
public static boolean checkMath(String s,String p,int i,int j){
if(i<=0||j<=0){
return false;
}
if(p.charAt(j-1)=='.'){
return true;
}
if(s.charAt(i-1)==p.charAt(j-1))
{
return true;
}
return false;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。