判断正则表达式是否匹配 Regular Expression Matching @LeetCode

前端之家收集整理的这篇文章主要介绍了判断正则表达式是否匹配 Regular Expression Matching @LeetCode前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

这道题真心容易错,总的来说思路是递归。

判断下一个字符是否是*:

如果不是*,则判断当前字符是否匹配。

如果是*,则因为不能确定*到底会匹配几个,在当前字符匹配的前提下,要枚举所有的情况,从假设匹配0个,1个,2个。。。只要有一种情况成功了,最终也就成功了。

如果是*,但是当前字符不匹配,则跳过两个递归。


http://discuss.leetcode.com/questions/175/regular-expression-matching

这里有更详细的解释。



package Level5;


/**
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
Discuss


 */
public class S10 {

	public static void main(String[] args) {
		System.out.println(isMatch("aa","a*"));		// true
		System.out.println(isMatch("aa","a"));		// false
		System.out.println(isMatch("aa","aa"));	// true
		System.out.println(isMatch("aaa","aa"));	// false
		System.out.println(isMatch("aa","a*"));	//true
		System.out.println(isMatch("aa",".*"));	// true
		System.out.println(isMatch("ab",".*"));	// true
		System.out.println(isMatch("aab","c*a*b"));		// true
		
		System.out.println(isMatch("","bab"));			// false
		System.out.println(isMatch("ab",".*c"));		// false
		System.out.println(isMatch("aaa","a.a"));		// true
		System.out.println(isMatch("a","."));			// true
		System.out.println(isMatch("a","ab*"));		// true
		System.out.println(isMatch("bb",".bab"));		// false
		System.out.println(isMatch("bb","*"));			// false		
		
	}

	public static boolean isMatch(String s,String p) {
		return isM(s,p,0);
	}
	
	public static boolean isM(String s,String p,int i,int j){
		if(j >= p.length()){			// pattern已经用光
			return i >= s.length();	// 如果s已经走完则匹配,否则不匹配
		}
		if(j == p.length()-1){	// 如果pattern的j已经走到最后一个字符,如果想匹配,则s的i也必须在最后一个,且相等
			return (i == s.length()-1) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
		}

		// 如果pattern的下一个字符(j+1)不是*
		if(j+1<p.length() && p.charAt(j+1) != '*'){
			if(i == s.length()){	// 如果s已经走完,则说明不匹配
				return false;
			}
			if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.'){	// 如果当前字符匹配
				return isM(s,i+1,j+1);		// 继续下一个字符判断
			}else{	// 如果当前字符不匹配,直接返回false
				return false;
			}
		}
		
		// 如果下一个字符(j+1)是* 且 当前字符匹配,则进行搜索:
		while(i<s.length() && j<p.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')){
			// 因为*可以取0,1,2,...所以i=i,i+2,...对所有可能进行测试
			// 最后能否匹配取决于剩下的匹配是否成功
			if(isM(s,i,j+2)){	// 只要找到一个匹配成功即可
				return true;
			}
			i++;
		}
		
		// 如果下一个字符(j+1)是* 且 当前字符不匹配,则pattern跳过两个,继续比较
		// 还有一种情况到这里是上面的最后一次尝试(i==s.length())
		return isM(s,j+2);
	}

}
原文链接:https://www.f2er.com/regex/362199.html

猜你在找的正则表达式相关文章