每天一道剑指offer-正则表达式匹配

正则表达式匹配

题目描述

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

解析

使用 指向 中下一个要匹配的字符，使用 指向 中剩下的模式串的首字符

如果 ，表示模式串消耗完了，这时如果 仍有字符要匹配那么返回 否则返回

如果 ，表示要匹配的字符都匹配完了，但模式串还没消耗完，这时剩下的模式串必须符合 这样的范式以能够作为空串处理，否则返回

和 都未越界，按照 后面是否是 来讨论

后面如果是 ，又可按照 是否能够匹配 分析：

，这时可以选择匹配一个 并继续向后匹配（不用跳过 和其后面的 ），也可以选择将 和其后面的 作为匹配空串处理，这时要跳过 和 其后面的

，只能作为匹配空串处理，跳过

后面如果不是 ：

， 同时后移一个继续匹配

，直接返回

已获授权