正则表达式匹配对“.”的支持和'*'[关闭]

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

。匹配任何单个字符。*匹配前面的元素中的零个或多个。匹配应该覆盖整个输入字符串(而不是部分)。

一些例子:

isMatch(aa,a)false

isMatch(aa,aa)true

isMatch(aaa,aa)false

isMatch(aa,a*)为真

isMatch(aa,.*)true

isMatch(ab,.*)true

isMatch(aab,c*a*b)true

作者给出了以下解决方案,真的很漂亮。

bool isMatch(const char *s, const char *p) {
  assert(s && p);
  if (*p == '\0') return *s == '\0';

  // next char is not '*': must match current character
  if (*(p+1) != '*') {
    assert(*p != '*');
    return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
  }
  // next char is '*'
  while ((*p == *s) || (*p == '.' && *s != '\0')) {
    if (isMatch(s, p+2)) return true;
    s++;
  }
  return isMatch(s, p+2);
}

作者还提出了一些进一步的思考:

如果你仔细思考,你可以利用上面代码以指数复杂度运行的一些情况。

你能想出一些例子吗?你将如何制作上述代码 更高效?

我提出了一个需要很长时间才能得到结果的案例,而 字符串s和p的长度并不很大。

s[]=“aaaaaaaaaa” p[]=“a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*

有人能帮我核实一下这个答案吗? 如何看待这种发现极端的测试问题?