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

【解题思路】先来判断p是否为空,若为空则根据s的为空的情况返回结果。当p的第二个字符为号时,由于号前面的字符的个数可以任意,可以为0,那么我们先用递归来调用为0的情况,就是直接把这两个字符去掉再比较,或者当s不为空,且第一个字符和p的第一个字符相同时,我们再对去掉首字符的s和p调用递归,注意p不能去掉首字符,因为号前面的字符可以有无限个;如果第二个字符不为号,那么我们就老老实实的比较第一个字符,然后对后面的字符串调用递归

【考查内容】字符串

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() > 1 && p[1] == '*') {
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
        } else {
            return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
    }
};
上一篇:#leetcode10正则表达式匹配


下一篇:正则表达式匹配