[leetcode]Regular Expression Matching

新博客地址：

[leetcode]Regular Expression Matching

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

 这道题不难，但是烦，就是匹配简单的正则表达式，算法也很简单：

写道

由于*写在字符的后面，因此采取从后往前匹配，省的每读一个数还要看看它后面的字符是不是*，事实也证明，逆向匹配效率也更高
定义p为正则表达式，s为字符串。
分情况考虑：
1. p的最后一个字符是普通字符c，则s的最后一个字符（如果存在）也是c，则将p和s的最后一个字符都删去，比较剩下的子串，否则返回false
2. p的最后一个字符是‘.’ ，如果s的长度>0，将p和s的最后一个字符都删去，比较剩下的子串，否则返回false
前两种的处理比较简单，麻烦的是下面的
3. p的最后一个字符是‘*’，又分为三种情况：

3.1 其前驱字符是普通字符，记为a，对p继续往前遍历，看a*前面还有几个a，并记录其个数letterCountInP，比如aaaaa*的letterCountInP = 4。同理对s进行遍历，看字符结尾有几个a，记录其个数letterCountInS，比如baaa的letterCountInS = 3。
如果letterCountInP > letterCountInS则返回false（如上面举得例子）
否则进行swallow，这里我是用的reluctant匹配法，也可以用greedy匹配原则，其实时间复杂度是一样的。具体可以看代码。

3.2 其前驱字符是‘.’，这种情况稍微简单一点，直接尝试对整个s字符串进行匹配，同样采取reluctant匹配法

3.3其他情况，返回false

 代码如下：

public boolean isMatch(String s, String p) {
		if (s == null || p == null) {
			return s == p ;
		}
		if ((!p.contains("*") && !p.contains(".")) || (s.length() == 0 && p.length() == 0)) {
			return s.equals(p);
		}
		Set<Character> letterSet = new HashSet<Character>(Arrays.asList('q','w','e','r','t','y','u','i','o','p','a','s','d','f','g','h','j','k','l','z','x','c','v','b','n','m'));
		int tail = p.length() - 1;
		if (letterSet.contains(p.charAt(tail))) {
			if (s.length() >= 1 && p.charAt(tail) == s.charAt(s.length() - 1)) {
				return isMatch(s.substring(0, s.length() - 1), p.substring(0, tail));
			}
			return false;
		}else if(p.charAt(tail) == '.'){
			if(s.length() > 0)return isMatch(s.substring(0, s.length() - 1), p.substring(0, tail));
			return false;
		}else{// *
			// when we met with * we need to check the former letter of it
			//1. if it is a normal letter
			/*
			 * for instance a*, we should also check how many a before a* in p ,and how many a in s,
			 * if there are n 'a' before in p and m 'a' in s,we can just swallow m - n 'a' (if m - n < 0 ,return false)
			 */
			//2. if it is a .
			/* just have a shoot ,swallow none ,then one ,two ,three.... check each 
			 */
			//3. if it is a * return false;
			if(tail == 0) return false;
			else{
				char pre = p.charAt(tail - 1);
				if(letterSet.contains(pre)){
					int letterCountInP = 0,letterCountInS = 0; 
					for(int i = s.length() - 1; i >= 0; i--){
						if(s.charAt(i) == pre){
							letterCountInS++;
						}else break;
					}
					for(int i = tail - 2; i >= 0; i--){
						if(p.charAt(i) == pre){
							letterCountInP++;
						}else break;
					}
					if(letterCountInS < letterCountInP) return false;
					for(int i = 0; i <= letterCountInS; i++){
						if(isMatch(s.substring(0, s.length() - i), p.substring(0, p.length() - 2 - letterCountInP))){
							return true;
						}
					}
					return false;
				}else if(pre == '.'){
					for(int i = 0; i <= s.length(); i++){
						if(isMatch(s.substring(0, s.length() - i), p.substring(0, p.length() - 2))){
							return true;
						}
					}
					return false;
				}else return false;
			}
		}
	}