【LeetCode-10】10. 正则表达式匹配

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

解题思路1：递归回溯

递归回溯，其实就是将所有可能的情况全部都试一遍

实现函数isMath(String s, String p) ：通过不停的减去s和p相同的首部，直到某一个或者两个都被减空，就可以得到结论（还需要结合所有剪空的情况）。

首先从没有“*”的情况看，只需要扫描一遍s和p，从首部开始比较对应位置的元素是否相同即可，如果相同就可以剪去，比较下一个即可：

// 第i个下标位置元素的比较 , '.'代表任何元素
s[i] == p[i] || p[i] == '.'

现在添加’’，需要注意题目的要求：’‘前面的元素可以出现0次或者多次，那么注意检测到p中第i个元素的下一个元素为’*'时，就会有两个情况：

1. p的第i个元素在s中出现0次：此时，保持s不变，将p剪去2个元素（将*和前面的一个元素剪去），继续调用函数isMatch。如：s=‘bb’，p=‘a*pp’，将p的首部2个元素剪去，得到p=‘bb’，继续比较；

2. p的第i个元素在s中出现一次或者多次：此时，比较i元素和s的首元素，如果相同（注意，这个前提条件），剪去s的首元素，保持p不变，继续调用isMatch函数。 如：s=‘aabb’，p=‘a*bb’, 那么比较首元素相同，再剪去s的首元素，得到s=‘abb’，再调用isMatch比较。

当然会出现这种情况：s=‘abb’， p=‘aabb’; 按1来说，p剪去两个元素，s=‘abb’, p=‘abb’, 成功；按照2来说，s=‘bb’, p='aabb’ , 失败。

所以，这会把所有的情况全部试一遍，就可以得到结果。

class Solution {
    public boolean isMatch(String s, String p) {
        //在p为空串后，只需要查看s是否为空即可
        if(p == null || p.length() == 0) {
            return s == null || s.length() == 0;
        }
        //查看两个字符串首元素是否一致,注意要先判断s不为空
        boolean first_match = s.length() != 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.' );
        //如果下一个字符是‘*’
        if(p.length() >= 2 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p));
        } else {
            //一般情况
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
    }
}

动态规划

讲的很好的视频

class Solution {
    public boolean isMatch(String s, String p) {
	    	//dp[i][j] = string s with len i matches string p with len j.这句话一定要懂
	    	//默认都是false
	    	boolean [][]dp=new boolean[s.length()+1][p.length()+1];
	    	
	    	dp[0][0]=true;
	    	//当s为null时，看p的情况 
	    	for(int i=1;i<=p.length();i++) {
	    		if( p.charAt(i-1)=='*' && dp[0][i-2]) {
	    			dp[0][i]=true;
	    		}
	    	}
	    	
	    	// s:ab
	    	// p:a.  ab  ab*  ab.*   (aa*  aa.*)
	    	for(int i=1;i<=s.length();i++) {
	    		for(int j=1;j<=p.length();j++) {
	    			if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.') {
	    				dp[i][j]=dp[i-1][j-1];
	    			}else if(p.charAt(j-1)=='*') {
	    				if(p.charAt(j-2)!='.' && p.charAt(j-2)!=s.charAt(i-1)) {
	    					dp[i][j]=dp[i][j-2];
	    				}else {
	    				dp[i][j]=(dp[i][j-2] || dp[i][j-1] || dp[i-1][j]);	
	    				}
	    			}
	    		}
	    	}
	    	return dp[s.length()][p.length()];
	    }
}