LeetCode 004 简单的正则语言匹配器

Qustion:

Implement regular expression matching with support for ‘.’ and ‘*’.

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

Coding:

拿到这道题的时候会有一种似曾相识的感觉，在吴军所著的《代码之美》这本书里，曾经记录了一种简单的，使用递归实现的正则语言匹配器，作者是Rob Pike，他也是《The Practice of Programming》的作者。这个简单的正则语言匹配器用递归实现，具备基本的正则匹配功能：

c 匹配任意的字母c
.（句点）匹配任意的单个字符
^ 匹配输入字符串的开头
$ 匹配输入字符串的结尾
* 匹配前一个字符的零个或者多个出现

而代码只有短短的三十几行：

int match(char *regexp, char *text)
{
	if (regexp[0] == '^')
		return matchhere(regexp+1, text);
	do { /* must look even if string is empty */
		if (matchhere(regexp, text))
			return 1;
	} while (*text++ != '\0');
	return 0;
}
/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
	if (regexp[0] == '\0')
		return 1;
	if (regexp[1] == '*')
		return matchstar(regexp[0], regexp+2, text);
	if (regexp[0] == '$' && regexp[1] == '\0')
		return *text == '\0';
	if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
		return matchhere(regexp+1, text+1);
	return 0;
}
/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
	do { /* a * matches zero or more instances */
		if (matchhere(regexp, text))
			return 1;
	} while (*text != '\0' && (*text++ == c || c == '.'));
	return 0;
}

参考这样的思路，一种利用递归实现的正则语言匹配器的算法是很容易想到的，因为leetcode上的题中需要考虑的情况更少，只有 . 和 * ，因此很容易想到如下的算法：

bool isMatch(char *s, char *p)
{
	if (*p == '\0')
		return *s == '\0';
	if (*(p + 1) != '*')
		return *s != '\0' && ((*p == *s) || (*p == '.')) && isMatch(s + 1, p + 1);
	do { /* *(p+1) == '*' */
		if (isMatch(s, p + 2))
			return 1;
	} while (*s != '\0' && (*s++ == *p || *p == '.'));
	return 0;
}

在最后的do/while中，当s子串和p+2对应的规则不再匹配，且s子串的起始位置不再和p中 * 前的字符相匹配时（s无法再后移起始位置），表示以无匹配情况，此时结束程序。这个递归算法的缺点在于时间复杂度和空间复杂度较高，如果存在很多 * 符号，会让每一层递归程序都不幸地跑在循环里，有可能出现指数级复杂度。上面的代码在leetcode上运行的时间是19ms。

下面有一种动态规划的方法也能解决这个问题，且时间复杂度相对更好，运行实测时间是9ms。要用动态规划，我们首先要明白状态之间的关系。我们让dp[i][j]代表前i个字符和前j个规则是否匹配，这里有一个小点比较容易混淆，就是s[i-1]和p[j-1]代表第i个字符和第j个关系。
于是我们有了如下的关系：

当第j个规则不是 * ：

dp[i][j] = (i>0) && dp[i-1][j-1] && ((p[ind_p-1] == .) || (p[ind_p-1] == s[ind_s-1]));
当第j个规则是 * ：

dp[i][j] = dp[i][j-2] || ((i>0) && dp[i-1][j] && (s[ind_s-1] == p[ind_p-2] || p[ind_p-2] == .));

注：此处有两种情况，或者是(x*)整个不取，或者是取>=1次。若是整个不取，则dp[i][j]的状态应该和(x*)之前的规则一致；若是取>=1次，则dp[i][j]的状态应该综合考虑前一个字符和当潜规则的状态以及当前字符是否能用(x*)表示。

由此我们可以写出相应算法：

dp[0][0] = 1;
for (ind_s = 0; ind_s <= len_s; ind_s++) {
	for (ind_p = 1; ind_p <= len_p; ind_p++) {
		if (p[ind_p-1] != '*') {
			dp[ind_s][ind_p] = ind_s>0 && dp[ind_s-1][ind_p-1] && ((p[ind_p-1] == '.') || (p[ind_p-1] == s[ind_s-1]));
		} else if (p[ind_p-1] == '*') {
			dp[ind_s][ind_p] = dp[ind_s][ind_p-2] || (ind_s>0 && dp[ind_s-1][ind_p] && (s[ind_s-1] == p[ind_p-2] || p[ind_p-2] == '.'));
		}
	}
}

其中len_s/len_p分别表示字符串和规则的长度，ind_s/ind_p分别表示当前dp的下标。这个方法要考虑的情况比较多，但是时间复杂度更优秀。

完整代码可参见我的Github: RegularExprMatching.c

Boyi Li

LeetCode 004 简单的正则语言匹配器

Qustion:

Coding:

Reference: