leetcode-10-Regular Expression Matching模拟正则匹配

模拟正则表达式中的 . 和 * 号匹配字符串    :https://leetcode.com/problems/regular-expression-matching  


Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

 

 

设i = j = 0.

不是*号可以直接匹配成功,i++,j++ .继续比较下一个字符。

————————————————可以倒着比较,遇到*号就不用考虑越界(*号前面一定有字符。道理是一样的:

    class Solution {
       public boolean isMatch(String s, String p) {
           int i = s.length();
           int j = p.length();
           return help(s,i-1,p,j-1);
       }
       
       public boolean help(String s,int i,String p, int j){
    
           if(j < 0){
               if(i < 0)
                   return true;
               else
                   return false;
           }
    
           if(p.charAt(j) == '*'){//为* j一定大于0
               if(i >= 0 &&(p.charAt(j-1) == s.charAt(i) || p.charAt(j-1)=='.')){
                   if(help(s,i-1,p,j))
                       return true;
               }
               return help(s,i,p,j-2);
           }
    
           if(i >= 0 && (s.charAt(i) == p.charAt(j) || p.charAt(j)=='.')){
               return help(s,i-1,p,j-1);
           }
           return false;
       }
    }
    

动态规划:

使用二维数组dp[][]保存信息,  dp[i][j]表示 s[0]-s[i] 与 p[0]-p[j] 是否匹配. true ,false 表示.

       public boolean isMatch(String s, String p) {
    
           if (s == null || p == null) {
               return false;
           }
           boolean[][] dp = new boolean[s.length()+1][p.length()+1];
           dp[0][0] = true;
           for (int i = 0; i < p.length(); i++) {
               if (p.charAt(i) == '*' && dp[0][i-1]) {
                   dp[0][i+1] = true;
               }
           }
           for (int i = 0 ; i < s.length(); i++) {
               for (int j = 0; j < p.length(); j++) {
                   if (p.charAt(j) == '.') {
                       dp[i+1][j+1] = dp[i][j];
                   }
                   if (p.charAt(j) == s.charAt(i)) {
                       dp[i+1][j+1] = dp[i][j];
                   }
                   if (p.charAt(j) == '*') {
                       if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                           dp[i+1][j+1] = dp[i+1][j-1];
                       } else {
                           dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                       }
                   }
    
               }
           }
           return dp[s.length()][p.length()];
       }
0

Powered by Jekyll and Theme by solid