LeetCode 10. Regular Expression Matching

LeetCode 10. Regular Expression Matching

题目

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

'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some 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

分析

字符串匹配的要求是： - ‘*’代表前一个数字的个数乘0~n倍。 - ‘.’可以代表任何一个字符。 - 两个字符串必须完全一样，即并不是仅仅匹配部分

这道题难度不高，但是需要想一下逻辑关系，下面是我针对这道题采取的策略：

从后往前用p去匹配s，因为字符串s的长度和形式是不会发生变化的，用p来匹配它更为方便。用两个模式分别代表检索到’*’和未检索到’*’。若检索到’*’则需要考虑在可接受的情况下，对前一个字符分别乘0~n的处理。有一个特殊情况就是匹配完s后p可能还剩有几个数，若剩下的几个数可以通过’*’消去，则这么做。

代码实现

class Solution { public: bool isMatch(string s, string p) { //从后到前 匹配 s 和 p int index_p = p.size() - 1; int index_s = s.size() - 1; //mod == true 代表前一个是字母 //mod == false 代表前一个是* bool mod = true; while(index_s >= 0 && index_p >= 0) { if (mod) { if (s[index_s] == p[index_p] || p[index_p] == '.') { index_p--; index_s--; } else if (p[index_p] == '*') { mod = false; index_p--; if (isMatch(s.substr(0, index_s + 1), p.substr(0, index_p)))return true; } else return false; } else { if (s[index_s] == p[index_p] || p[index_p] == '.') { if ( isMatch(s.substr(0, index_s), p.substr(0, index_p)) )return true; index_s--; } else if (p[index_p] == '*')index_p--; else { mod = true; index_p--; } } } mod = false; while (index_p > index_s) { if ( p[index_p] == '*') { index_p--; mod = true; } else if (mod) { index_p--; mod = false; } else break; } return index_s == index_p; } };