LeetCode 10 Regular Expression Matching 正则匹配

前端之家收集整理的这篇文章主要介绍了LeetCode 10 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

翻译:正则匹配。两个字符串匹配。.可以代替任意一个字符。*可以表示前一个字符出现的次数为0次或者多次。注意,这个*不是代表任意0个到多个字符。而是值得前面的字符出现次数。表示刚开始做的时候想成了编译的NFA。

一开始看这个题目确实有些蒙住了。上午上课期间想了想,没有找到好的办法解决。于是乎搜了一下大神的代码,学习了一下思想。并自己尝试写了出来。
代码
 public static boolean isMatch(String s,String p) {
		return Bf(s,p,0);
    }
	public static boolean Bf(String s,String p,int i,int j)//brute force算法
	{
		if(j == p.length())//如果一个到了结尾, 判断另一个是否结束,结束则T,否则F
			return i == s.length();
		if(j == p.length()-1||		//P串到结尾
				p.charAt(j+1)!='*')//p下一个不是*
		{
			if(i == s.length()||  //S串已经走完
				s.charAt(i)!=p.charAt(j)&&p.charAt(j)!='.'	)
				return false;
			return Bf(s,i+1,j+1);//匹配成功,则继续下一个
			
		}
		for(;i<s.length()&&(p.charAt(j)=='.'||p.charAt(j)==s.charAt(i));i++)
		{
			if(Bf(s,i,j+2))//因为此时p.charAt(j+1) 为*,此时应该跳过当前和下一个*去匹配下一个字符,如果下一个字符之后都匹配,则成功。
			                    //否则 i++,知道把*代表的字符全部都匹配出来后在继续。
				return true;
		}
		return Bf(s,j+2);
				
		
	}

采用的算法是brute force算法,模式匹配算法的一种。

Brute-Force算法:

也称简单匹配算法,其基本思路是:从目标串s=”s0s1…sn-1”的第一个字符开始和模式串t=”t0t1…tm-1”中的第一个字符比较,若相等,则继续逐个比较后续字符,否则,从目标串s的第2个字符开始重新与模式串t的第一个字符进行比较,依次类推,若从目标串s的第i个字符开始,每个字符依次和模式串t中的对应字符相等,则匹配成功,该算法返回i;否则匹配失败,返回-1。

犹记得大二数据结构讲了一个KMP的算法。现在怎么写完全想不起来了。等会复习之。
刚才看了下这道题的标签,要用动态规划。表示动态规划没有学习过。等会学习之~

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