剑指offer-正则表达式动态规划

1.请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

题目链接：力扣

本题疑惑： j-2不会发生数组角标越界吗，还是数组一开始初始化解决了这个问题

class Solution {    public boolean isMatch(String s, String p) { //dp[i][j]代表添加s的第i-1个元素，添加p的第j-1个元素时的值； int m = s.length()+1;//这里加1 int n = p.length()+1; boolean dp[][] = new boolean[m][n]; //dp初始化 dp[0][0]=true; //dp首行初始化，防止越界 for(int j=2;j<n;j+=2){     //j-1是代表p数字的奇数为*，那样前面的值才可以消除成为长度为0的     dp[0][j]=dp[0][j-2] && p.charAt(j-1)=='*'; } //开始遍历这两个字符串,上面初始化0了，下面不用从0开始 for(int i=1;i<m;i++){     for(int j=1;j<n;j++){  //第一种情况 p[j-1]=*,这样会牵扯到p[j-2]  if(p.charAt(j-1)=='*'){//这里p的j-2个元素是关键，可以出现0次，可以跟s的i-1匹配，可以和.*表示任意字符      //1.p数组的j-1个字符*，可以让j-2个字符消失，所以dp[i][j]=dp[i][j-2];      if(dp[i][j-2]) dp[i][j]=true;//对p来说，p添加元素      //2.p不添加元素，根据末尾      //j-2个字符不消失，sp同时添加元素，此时p的j-1个字符跟j-2个字符相等      else if(dp[i-1][j] && s.charAt(i-1)==p.charAt(j-2)) dp[i][j]=true;      else if(dp[i-1][j] && p.charAt(j-2)=='.') dp[i][j]=true;//.*可以匹配任意元素  }else{      //第二种情况只会牵扯到p[j-1]      if(dp[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)) dp[i][j]=true;      else if(dp[i-1][j-1] && p.charAt(j-1)=='.') dp[i][j]=true;  }     } } return dp[m-1][n-1];    }}