Ex19 正则表达式匹配

题目描述

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

解题思路

本题最重要的是对*的妥善处理。

除*外，字符匹配成功的情况还包括p[0] = '.'时（s[0]为任意）所以，当字符成功匹配时，第二个字符是*，存在着三种情况：

• 继续进行下一个比较：isMatch(s+1, p+2)；
• 把*当做1次匹配：is_match(s+1, p)；
• 把*当作0次匹配：is_match(s, p+2)。

当字符匹配不成功且第二个字符为*时，唯一的情况是把*当作0次匹配。

代码

bool
isMatch (char *s, char *p)
{
  if (!s || !p)
    return false;
  if (s[0] == '\0' && p[0] == '\0')
    return true;
  if (s[0] != '\0' && p[0] == '\0')
    return false;
  if (p[1] == '*')
    {
      if (p[0] == s[0] || (p[0] == '.' && s[0] != '\0'))
        return isMatch (s + 1, p + 2) || isMatch (s + 1, p)
               || isMatch (s, p + 2);
      return isMatch (s, p + 2);
    }
  else if (s[0] == p[0] || (p[0] == '.' && s[0] != '\0'))
    return isMatch (s + 1, p + 1);
  return false;
}

结果

执行结果：通过

执行用时：1020 ms, 在所有 C 提交中击败了13.97%的用户

内存消耗：5.4 MB, 在所有 C 提交中击败了17.16%的用户