image.png

解题思路

回溯

image.png

  1. public boolean isMatch(String s, String p) {
  2.     //如果正则串p为空字符串s也为空这匹配成功，如果正则串p为空但是s不是空则说明匹配失败
  3.     if (p.isEmpty())return s.isEmpty();
  4.     //判断s和p的首字符是否匹配，注意要先判断s不为空
  5.     boolean headMatched=!s.isEmpty()&&(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.');
  6.     if (p.length()>=2&&p.charAt(1)=='*'){//如果p的第一个元素的下一个元素是*
  7.         //则分别对两种情况进行判断
  8.         return isMatch(s,p.substring(2))||
  9.             (headMatched&&isMatch(s.substring(1),p));
  10.     }else if (headMatched){//否则，如果s和p的首字符相等
  11.         return isMatch(s.substring(1),p.substring(1));
  12.     }else {
  13.         return false;
  14.     }
  15. }

动态规划

本题的dp数组的含义就是：dp[i][j]就是s的前i个元素是否可以被p的前j个元素所匹配。
image.png

  1. public boolean isMatch(String s, String p) {
  2.     //需要分别取出s和p为空的情况，所以dp数组大小+1
  3.     boolean[][] dp=new boolean[s.length()+1][p.length()+1];
  4.     //初始化dp[0][0]=true,dp[0][1]和dp[1][0]~dp[s.length][0]默认值为false所以不需要显式初始化
  5.     dp[0][0]=true;
  6.     //填写第一行dp[0][2]~dp[0][p.length]
  7.     for (int k=2;k<=p.length();k++){
  8.         //p字符串的第2个字符是否等于'*',此时j元素需要0个，所以s不变p减除两个字符
  9.         dp[0][k]=p.charAt(k-1)=='*'&&dp[0][k-2];
  10.     }
  11.     //填写dp数组剩余部分
  12.     for (int i=0;i<s.length();i++){
  13.         for (int j=0;j<p.length();j++){
  14.             //p第j个字符是否为*
  15.             if (p.charAt(j)=='*'){
  16.                 //两种情况:1.s不变[i+1],p移除两个元素[j+1-2]。
  17.                 // 2.比较s的i元素和p的j-1(因为此时j元素为*)元素,相等则移除首元素[i+1-1],p不变。
  18.                 dp[i+1][j+1]=dp[i+1][j-1]||
  19.                     (dp[i][j+1]&&headMatched(s,p,i,j-1));
  20.             }else {
  21.                 //s的i元素和p的j元素是否相等,相等则移除s的i元素[i+1-1]和p的j元素[j+1-1]
  22.                 dp[i+1][j+1]=dp[i][j]&&headMatched(s,p,i,j);
  23.             }
  24.         }
  25.     }
  26.     return dp[s.length()][p.length()];
  27. }
  28. //判断s第i个字符和p第j个字符是否匹配
  29. public boolean headMatched(String s,String p,int i,int j){
  30.     return s.charAt(i)==p.charAt(j)||p.charAt(j)=='.';
  31. }