Regular Expression Matching

原题

'.' 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

实际中的正则表达式很复杂，设计的符号也很多，这里只是简单了列举了两个符号：

.(dot)——可以匹配一个任意字符。

* -——出现在行首没意义，属于结合性的字符，必须依赖其前面的字符，表示前面的字符出现0次或多次。".*"中*与.结合，而不关注.具体跟哪个字符匹配。

比较特殊的字符就是 *，它会决定前面的字符是单独存在，还是要与*结合，即*前面的字符不能决定自己的出现次数，因为若其后不跟*，则其出现一次是肯定的，而当其后紧跟*时，其出现次数就不确定，那么这个字符到底要出现多少次才能使得两个串匹配，亦或无论出现多少次都不匹配，这些可能性就需要一一的去验证。

class Solution {
public:
	bool isMatch(const char *s,const char *p) {
	if(*p == '')  return *s == '';
	if (*(p + 1) != '*') { //naive character
		if(*s != '' &&(*s == *p || *p == '.'))//
			return isMatch(s + 1,p + 1);
		else
			return false;
	}
	
	//else join with '*'
	while (*s == *p || (*s != '' && *p == '.'))
	{
		if(isMatch(s,p + 2)) return true;
		++s;
	}
    // '*' should just to be 0.
	return isMatch(s,p + 2);
	}
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!