LeetCode.10 正则表达式匹配

leetcode

题目描述

给定一个字符串，以及一个正则表达式。
判断给定的正则表达式是否可以表示字符串。

这里并没有让所有的正则表达式的符号都参与进来。
只是让’*’, ‘.’这两个符号加进来了。且字符串中只有a~z小写。

* 吃掉前面的字符，或者无视自己，或者把前面的字符重复x次。
. 可以匹配任意字符

比如

a*有好几种解释
1. 空串后面的*把a吃掉
2. a, *自身没有起任何作用
3. aa重复1次
4. aaa重复2次

注意

.* 万能字符串，可以表示任何字符在重复的时候，也可以写成....这样。
** 后面的*可以选择吃掉前面的字符。前面的字符*可能的一种选项就是忽略自己。
   1. 空串
   2. *
   3. **
   4. ***

解法

这个题的做法是典型的深度优先搜索。不过在处理的时候，可以考虑预处理一下。

1. x*x*如果出现在正则表达式里面。实际上是可以简化成x*的。
2. x*x*x*可以优化成x*

预处理的代码如下：

bool isMatch(char* s, char* p) {
    int len_p = strlen(p);
    int i;
    for (i = len_p - 1; i > 1; --i) {
        // 匹配x*x*这种情况, i指向后面的那个x
        if (p[i - 1] == '*' && p[i + 1] == '*' && p[i] == p[i - 2]) {
            memmove(p + i, p + i + 2, len_p - i - 1);
        }
    }
    // 经过上面的处理，x*x*x*可以被缩减为x*
    // 这里开始进行match匹配
    return match_sub(s, p);
}

在进行匹配的时候，首先可以考虑没有'*'号的情况。比如。

abc 与 a.c
abc 与 bdc
""  与 pg
NULL 与 abc

这种都特别容易判断。

#define same(a,b) ((a)==(b) || ('.') == (b))
bool match_sub(char *s, char *p) {
    for (;*p && *(p + 1) != '*'; ++s, ++p)
        if (!s|| !*s || !same(*s, *p))
            return false;
    ...
    // 此时*p == 0或p[1] == '*'
    if (!*p) return NULL == s || *s == 0;
    // 此时p[1] 必然为'*'
    
    // 如果当前字符相等，此时p[1] == '*'
    // 那么可以选择
    // 1. 重复 match_sub(s+1, p)
    // 2. 利用*吃掉当前字符 match_sub(s, p+2);
    // 3. a*b, *号可以选择无视自己.那么就是match_sub(s+1, p+2);
    if (*s && same(*s, *p))
        return  match_sub(s + 1, p) || match_sub(s, p + 2) || match_sub(s+1, p+2);
    else
        return match_sub(s, p + 2);
    // 除此之外的其他情况，比如*s == 0 || !same
    // 那么只能利用*号吃掉当前字符
}