代码拉取完成，页面将自动刷新
这题刚开始见到，还以为遇到原题了，因为跟剑指offer的其中一题非常像，剑指offer第52题正则表达式，只不过那题给的两个char类型的数组，当时弱弱的用递归暴力过了。
然后一顿操作把上次递归的方法重写过来，结果超时了……
但是还是把这种递归的思路讲一下，递归主要进行匹配所有情况，主要是看当前位置两个串串能不能匹配。
需要考虑*情况可以匹配，因为*可以出现0次，1次多次。那么在遇到使用*的如果匹配了，可以通过递归实现下面三者方式
a*aa和aa这个第一个a*可以看成0次)a*aa和aaa转成aa和aa的匹配)a*和aaa转成a*和aa的匹配)同样，如果遇到*不可以匹配，那么就使用0次就行了(b*aa和aa匹配转换成aa和aa匹配)
如果下一个不是*，那就考虑是否相当或者模式字符是否为.进行继续匹配或者终止就可以，在考虑一些开始结束情况就可以了，一个大概的思维导图可以看一下。
这部分实现的代码如下：
public static boolean isMatch2(String s, String p) {
//System.out.println(s+" "+p);
if (p.length() == 0)// 模式串为false
{
if (s.length() == 0)
return true;
return false;
} else if (s.length() == 0) {// 匹配串为0
if (p.length() % 2 == 1)
return false;
else {
for (int i = 1; i < p.length(); i += 2) {
if (p.charAt(i) != '*')
return false;
}
return true;
}
} else if (p.length() == 1) {//匹配串长度为1
if((s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')&&s.length()==1)//可以匹配
return true;
else {
return false;
}
} else {// 两个串串正常长度
if(p.charAt(1)=='*')//下一个为*
{
if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')//可以匹配 分别用0次 用若1次 用若干次
{
return isMatch(s.substring(1), p)||isMatch(s.substring(1), p.substring(2))||isMatch(s, p.substring(2));
}
else {//不匹配只能用0次
return isMatch(s, p.substring(2));
}
}
else {
if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')
return isMatch(s.substring(1), p.substring(1));
else {//完全失败
return false;
}
}
}
很遗憾的超时了，不过在剑指offer是可以过的，主要遇到这种字符就会很麻烦：
isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*c")
因为这里面匹配中的a*任意一个都可以使用若干次导致递归种类太多爆栈。嘤嘤嘤。
这题正确而大众的解法当然是动态规划了，我们知道动态规划重在动态的规划方程。并且当前结果是基于父结果的。这题刚好就可以使用动态规划来解答。
我们使用我们声明一个dp[][]=new boolean[匹配串长度+1][模式串长度+1] 的二位数组用来储存结果， 其中dp[i][j]表示匹配串前i个和模式串前j个是否匹配。最终匹配串和模式串是否匹配就是返回dp[匹配串长度][模式串长度].
对于动态规划的问题，我们一般会空余出0号位放在越界等特殊情况，所以我们声明的二维数组大小长宽都大1，因为0号在dp[][]表示的是空串的结果而不是一号位置串的结果。然后我们在搞动态规划题一般需要以下几步：
这里的初始我们是dp[0][0]=true表示两个空串可以匹配。
我们分析这个dp[i][j] 匹配串前i个，模式串前j个是否匹配.其实这个分析和之前递归还是有点相似的：
首先如果模式串pattern第j个如果是*，以下两种情况任意一种匹配成功即可。
dp[i][j-2]==true那么dp[i][j]肯定为true，因为可以把它看成一个空串。
dp[i][j-2]不为true也不要紧,如果匹配串和模式串前一个字符可以匹配并且dp[i-1][j]为true，那么也可以匹配(a*和a )
如果模式串第j个不为*那么就是常规匹配了，如果当前位置字符不匹配，那么就为false，如果当前位置匹配且dp[i-1][j-1]==true那么dp[i][j]就为true：
当然，以上所有考虑i-1的情况i不能等于0.
综上分析得到dp方程为：
if(模式串当前为*)
dp[i][j]==dp[i][j-2]||(dp[i-1][j]&&两串当前字符可以匹配)
else
dp[i][j]=dp[i-1][j-1]&&两串当前字符可以匹配
具体实现需要注意下标编号在字符串位置和dp下标的含义，具体实现的代码为：
public static boolean isMatch(String s, String p) {
boolean dp[][]=new boolean[s.length()+1][p.length()+1];//默认为false
dp[0][0]=true;
for(int i=0;i<=s.length();i++)
{
for(int j=1;j<=p.length();j++)
{
if(p.charAt(j-1)=='*')//该位置为*
{
dp[i][j]=dp[i][j-2];//模式用了0次的看看是否能够匹配，能匹配最好，不能匹配继续
if(!dp[i][j])//不能匹配
{
if(i==0) {continue;}
else if(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.')//可以匹配
{
dp[i][j]=dp[i-1][j];
}
}
}
else {//正常字符
if(i==0){continue;}
else if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.') {//这个位置可以匹配
dp[i][j]=dp[i-1][j-1];
}
}
}
}
return dp[s.length()][p.length()];
}
原创不易，最后我请你帮两件事帮忙一下:
star支持一下， 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。