10. Regular expression matching

---

Preface

`
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 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/regular-expression-matching
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Sample correspondence model
Define 2D table
String validity check
str Can not have . and *
exp It can't start with *. Two * Not next to

	public static boolean isValid(char[] s, char[] e) {
    
		// s There can be no '.' or '*'
		for (int i = 0; i < s.length; i++) {
    
			if (s[i] == '*' || s[i] == '.') {
    
				return false;
			}
		}
		//  At the beginning e[0] It can't be '*', There is no adjacent '*'
		for (int i = 0; i < e.length; i++) {
    
			if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
    
				return false;
			}
		}
		return true;
	}

Recurrence of violence

Recursive meaning :
str from si Start and everything behind it , Can you be exp from ei Set out and all the matches behind it
It can be matched and returned true, otherwise false

1. ei The next position is not *
   If ei+1 No * , It means that I e There is no room for operation . It can't count on the following * Make it disappear , For this moment si Must be able to communicate with ei Right up
   Can only be [ei] The character is equal to [si] character
   or [ei] Character is a . , It can become everything

2. ei+1 yes *
   0) Change to zero
   

Give Way a* change 0 individual a, Match later
1) change 1 individual a
2) change 2 individual a
3) 3 individual a
4) 4 individual a

Every branch goes , But one goes through , Go straight back to true, All branches fail , return false,

	public static boolean isMatch1(String str, String exp) {
    
		if (str == null || exp == null) {
    
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		return isValid(s, e) && process(s, e, 0, 0);
	}

	// str[si.....]  Can you be  exp[ei.....] Match it out ！ true false
	public static boolean process(char[] s, char[] e, int si, int ei) {
    
		if (ei == e.length) {
     // exp  be without  str？
			return si == s.length;
		}
		// exp[ei] And the characters 
		// ei + 1 The character of position , No *
		if (ei + 1 == e.length || e[ei + 1] != '*') {
    
			// ei + 1  No *
			// str[si]  It has to be with  exp[ei]  Can match ！
			return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
		}
		// exp[ei] And the characters 
		// ei + 1 The character of position , yes *!
		while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
    
			if (process(s, e, si, ei + 2)) {
    
				return true;
			}
			si++;
		}
		return process(s, e, si, ei + 2);
	}

Slope optimization + Memory search

f(13, 29) Dependence

f(12, 29) Dependence
f(12, 29)=f(13,29)+f(12,31)
stay str in i Position character and str in i+ 1 This optimization exists when the position character is the same

When I am one - When a grid has enumeration behavior , I will observe the grid he has calculated , Can I replace it with a piece ,
Thus, we can get the value of this lattice one by one by using a finite number of positions

	public static boolean isMatch2(String str, String exp) {
    
		if (str == null || exp == null) {
    
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		if (!isValid(s, e)) {
    
			return false;
		}
		int[][] dp = new int[s.length + 1][e.length + 1];
		// dp[i][j] = 0,  I didn't count ！
		// dp[i][j] = -1  Yes , The return value is false
		// dp[i][j] = 1  Yes , The return value is true
		return isValid(s, e) && process2(s, e, 0, 0, dp);
	}

	public static boolean process2(char[] s, char[] e, int si, int ei, int[][] dp) {
    
		if (dp[si][ei] != 0) {
    
			return dp[si][ei] == 1;
		}
		boolean ans = false;
		if (ei == e.length) {
    
			ans = si == s.length;
		} else {
    
			if (ei + 1 == e.length || e[ei + 1] != '*') {
    
				ans = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process2(s, e, si + 1, ei + 1, dp);
			} else {
    
				if (si == s.length) {
     // ei ei+1 *
					ans = process2(s, e, si, ei + 2, dp);
				} else {
     // si It's not over 
					if (s[si] != e[ei] && e[ei] != '.') {
    
						ans = process2(s, e, si, ei + 2, dp);
					} else {
     // s[si]  You can talk to  e[ei] Deserve to go up 
						ans = process2(s, e, si, ei + 2, dp) || process2(s, e, si + 1, ei, dp);
					}
				}
			}
		}
		dp[si][ei] = ans ? 1 : -1;
		return ans;
	}