← 返回 citadel 的题目列表Regular Expression Matching
类型：online_judge
Implement a recursive algorithm to match a given input string and a pattern string. The pattern string can contain '.' and '', where '.' matches any single character and '' matches zero or more of the preceding element. Write a recursive algorithm to solve this problem and provide test cases.
Input
The input consists of two strings, s and p, representing the input string and the pattern string, respectively.
Output
Return true if the input string matches the pattern string, otherwise return false.
Example
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, so "aa" is a match.
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" matches zero or more of any character.
Constraints
0 <= s.length <= 20
0 <= p.length <= 30
Example
Input
aa
a