LeetCode 10. Regular Expression Matching

Posted on | In | |

题目描述

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”, “ca*b”) → true

即要求实现简单的包含'.'和'*'的正则表达式匹配。

算法分析

只需要注意有关'.'和'*'的匹配即可，每次可以只对s的第一位进行匹配，再进行递归实现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) {
            return s.empty();
        }
        if (p.length() >= 2 && p[1] == '*') {
            if (s.empty())
                return isMatch(s, p.substr(2));
            if (s[0] == p[0] || p[0] == '.')
                return isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
            return isMatch(s, p.substr(2));
        }
        else {
            if (s.empty())
                return false;
            if (p[0] == '.' || s[0] == p[0])
                return isMatch(s.substr(1), p.substr(1));
            return false;
        }
    }
};

本文为博主原创文章，转载请注明出处。