教育改变生活

标题: LeetCode真题-通配符匹配 [打印本页]

作者: 一秉 时间: 2020-8-11 16:30
标题: LeetCode真题-通配符匹配
题目描述
请实现支持'.'and'*'.的通配符模式匹配
'.' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。
匹配应该覆盖整个输入字符串（而不是部分）。
函数声明为：bool isMatch(const char *s, const char *p)
下面给出一些样例：
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
代码实现：
public class Solution {
public boolean isMatch(String s, String p) {
      int len1=s.length();
      int len2=p.length();
      char[] s1=s.toCharArray();
      char[] p1=p.toCharArray();
      boolean[][] dp=new boolean[len1+1][len2+1];
      dp[0][0]=true;
      for(int i=1;i<=len2;i++)
         if(p1[i-1]=='*')
            dp[0][i]=dp[0][i-2];
      for(int i=1;i<=len1;i++){
         for(int j=1;j<=len2;j++){
            if(p1[j-1]=='.'||p1[j-1]==s1[i-1]){
                  dp[i][j]=dp[i-1][j-1];
            }
            else if(p1[j-1]=='*'){
                  if(j!=1&&(p1[j-2]!='.'&&p1[j-2]!=s1[i-1]))
                     dp[i][j]=dp[i][j-2];
                     else
                        dp[i][j]=dp[i][j-2]||dp[i][j-1]||dp[i-1][j];
                  }
            }
         }
         return dp[len1][len2];
      }
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)