[leetcode] 10. Regular expression matching

10、 Regular Expression Matching

subject ：

Give you a string s And a character rule p, Please come to realize a support ‘.’ and ‘*’ Regular expression matching .

‘.’ Match any single character
‘*’ Match zero or more previous elements
Match , Is to cover Whole character string s Of , Instead of partial strings .

Example 1：

 Input ：s = "aa", p = "a"
 Output ：false
 explain ："a"  Can't match  "aa"  Whole string .

Example 2:

 Input ：s = "aa", p = "a*"
 Output ：true
 explain ： because  '*'  Represents the element that can match zero or more preceding elements ,  The element in front of here is  'a'. therefore , character string  "aa"  Can be regarded as  'a'  I repeated it once .

Example 3：

 Input ：s = "ab", p = ".*"
 Output ：true
 explain ：".*"  Means zero or more can be matched （'*'） Any character （'.'）.

Tips ：

1 <= s.length <= 20
1 <= p.length <= 30
s Only from a-z Lowercase letters of .
p Only from a-z Lowercase letters of , As well as the character . and *.
Ensure that characters appear every time * when , All of them are matched with valid characters

Their thinking ：

Words , This topic , Really? , Everyone understands it differently .

such as ： The meaning of matching zero or more preceding elements ： It can be understood as ： * and * front ( Set to x) As one ; perhaps * Elements before and * They are independent . These two understandings , Nothing wrong. .

The title is not difficult. , But the expression is really stretching .

Put aside the question of understanding , The best solution to this problem is to use state machine transfer .

The code is as follows ：

Life is too short , I use java.

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        return s.matches(p);
    }
}

Ha ha ha , Okay , No more noise , Get down to business .

Normal code ：

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
    
            for (int j = 1; j <= n; ++j) {
    
                if (p.charAt(j - 1) == '*') {
    
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
    
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
    
                    if (matches(s, p, i, j)) {
    
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
    
        if (i == 0) {
    
            return false;
        }
        if (p.charAt(j - 1) == '.') {
    
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}