Leetcode算法刷题 10.正则表达式匹配
前言
今天做了一道动态规划题目，Leetcode上的正则表达式匹配，分享下题解
题目连接:10. 正则表达式匹配
思路
本题一看就是一个动态规划，或者递归解法，不过递归就太耗时了。
整体思路如下:
首先将 正则表达字符串 p 转为为数据 pList,将通配符与其前字符划分为一个item，方便后面匹配
生成一个 二维数组
boolean dp = new boolean[N][M]，其中 N 是 pList长度，M是 待匹配字符串 s的长度。逐一遍历 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]; }
作者：陈序猿_Android
链接：https://juejin.cn/post/7006275288858361869