preface

Today I did a dynamic programming problem, Letcode regular expression matching, share the solution of the problem

10. Regular expression matching

Train of thought

So this looks like a dynamic program, or a recursive solution, but the recursion would take too long.

The overall idea is as follows:

1. First, the regular expression string P is converted into data pList, and the wildcard character and its preceding character are divided into an item to facilitate subsequent matching

2. Generate a two-dimensional array Boolean dp = new Boolean [N][M] where N is the pList length and M is the length of string s to be matched.

3. The pList is traversed one by one to match the characters in S. Obviously, in the matching rule, the position of the character in S from which the current match starts should start from the position where the last match can be matched.

   So if pList[I] matches s[j], let dp[I][j] =true; To record the match between the matching card at I and the character at j. Dp [I][j] = true; dp[I] = true; The site.

   If pList[I +1] is a wildcard, dp[I +1][j]=true; if pList[I +1] is a wildcard, dp[I +1][j]=true; If match, dp[I][j+e] = true, otherwise stop trying.

   Dp [I +1][j+1]=true if pList[I +1]= s[j+1], dp[I +1]=true

code

class Solution {
    public boolean isMatch(String s, String p) {
    	List<String> pList = getList(p);
    	int N = pList.size();
    	int M = s.length();
    	boolean[][] dp = new boolean[N][M];
    	int lastStart = -1;
    	int lastEnd = -1;
    	int j = 0,e=0;
    	boolean iMatch = false;
    	for(int i = 0; i<N; i++) { String cstr = pList.get(i);boolean isStar = isStar(cstr);
    		iMatch = false;
    		j = lastStart;
    		int tempLastEnd = lastEnd;
    		while(j<= tempLastEnd && j < M) {
    			if(j >= 0 && i-1> =0 && !dp[i-1][j] ) {++j;continue; }else if( j>=0 && i -1 <0) {++j;continue; }if (isStar) {/ / lastStart remains the same
    				iMatch = true;
    				if(j>=0) {
    					dp[i][j] = true;
    					lastEnd = j;
    				}
					e = j+1;
					while( e<M && match(cstr, s.charAt(e)) ) {
						dp[i][e] = true; lastEnd = e; e++; }}else if(j < M-1  && match(cstr, s.charAt(j+1))) {if(! iMatch) { lastStart = j +1;
					}
					iMatch = true;
					dp[i][j+1] = true;
					lastEnd = j+1;
				}
    			++j;
    		}
    		if(! iMatch)return false;

    	}

    	return dp[N-1][M-1];
    }
    private boolean match(String cstr,char c) {
    	return cstr.charAt(0) = ='. ' || cstr.charAt(0) == c;
    }
    
    private boolean isStar(String s) {
		return s.contains("*");
	}
    
    private List<String> getList(String p) {
    	List<String> spList = new ArrayList<String>();	
    	String s = "";
    	char c;
    	for(int i =0; i<p.length(); i++) { c = p.charAt(i);if (c == The '*') {
				spList.add(s+"*");
				s = "";
			} else {
				if(! s.isEmpty()) spList.add(s); s = c+""; }}if(! s.isEmpty()) spList.add(s);returnspList; }}Copy the code

Improve your code

In fact, the dp array above is actually a waste of space, because the slot at I, you only need to know the position in S where the last slot was matched. Modify the code as follows:

  public boolean isMatch(String s, String p) {
    	List<String> pList = getList(p);
    	char[] sArray = s.toCharArray();
    	int N = pList.size();
    	int M = s.length();
    	boolean[][] dp = new boolean[2][M];
    	int lastStart = -1;// The point where the last point started true
    	int lastEnd = -1;
    	int j ,e;
    	int t;
    	boolean iMatch;
		int tempLastEnd;
    	for(int i = 0; i<N; i++) { String cstr = pList.get(i);boolean isStar = isStar(cstr);
    		iMatch = false;
			tempLastEnd = lastEnd;
    		if (i>0) {
    			t = (i-1) %2;
			} else {
				t = -1;
			}
			j = lastStart;
			clear(dp,i%2,M);
    		while(j<= tempLastEnd && j < M) {
    			if(j >= 0 && t >=0 && !dp[t][j] ) {++j;continue; }else if( j>=0 && t <0) {++j;continue; }if (isStar) {/ / lastStart remains the same
    				iMatch = true;
    				if(j>=0) {
    					dp[i%2][j] = true;
    					lastEnd = j;
    				}
					e = j+1;
					while( e<M && match(cstr, sArray[e]) ) {
						dp[i%2][e] = true; lastEnd = e; e++; }}else if(j < M-1  && match(cstr, sArray[j+1]) {if(! iMatch) { lastStart = j +1;
					}
					iMatch = true;
					dp[i%2][j+1] = true;
					lastEnd = j+1;
				}
    			++j;
    		}
    		if(! iMatch)return false;
    	}
    	return dp[(N-1) %2][M-1];
    }
Copy the code