前言

今天做了一道动态规划题目，Letcode上的正则表达式匹配，分享下题解

题目连接:10. 正则表达式匹配

思路

本题一看就是一个动态规划，或者递归解法，不过递归就太耗时了。

整体思路如下:

1. 首先将 正则表达字符串 p 转为为数据 pList,将通配符与其前字符划分为一个item，方便后面匹配

2. 生成一个 二维数组boolean dp = new boolean[N][M]，其中 N 是 pList长度，M是 待匹配字符串 s的长度。

3. 逐一遍历 pList，去与S 中字符匹配.显然在匹配规则中，当前匹配符开始匹配的字符在 s 中的位置，应从上个匹配可匹配的位置开始。

   因此 如果 pList[i] 与 s[j] 匹配，则 让 dp[i][j] =true;来记录 i 处匹配符与 j处字符匹配。而下个 匹配符 i + 1,则应该遍历dp[i]纬度下所有 dp[i][j] = true;的地点。

   （1）如果 pList[i+1]为通配符，则 dp[i+1][j]=true,且 记录尝试匹配pList[i+1] 是否匹配 s[j+1]、s[j+e]… 如匹配，则dp[i][j+e] = true，否则停止尝试。

   （2）如果 pList[i+1]为非通配符，则判断 pList[i+1] 是否匹配 s[j+1],匹配则dp[i+1][j+1]=true.

代码

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 不变
    				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 == '*') {
				spList.add(s+"*");
				s = "";
			} else {
				if(!s.isEmpty())
					spList.add(s);
				s = c+"";
			}
    	}
    	if(!s.isEmpty())
			spList.add(s);
    	return spList;
    }
    
    
}
复制代码

改进代码

事实上以上dp数组其实浪费了很多空间，因为 i 处匹配符，只需要知道上一次匹配符是匹配的 s中的位置。修改代码如下:

  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;//上个点开始 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 不变
    				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];
    }
复制代码