题目描述
Given an input string (s) and a pattern (p), 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).
Example1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like . or *.
解题思路
- 剑指offer原题
- 注意 这里如果按C++字符串处理的话，会报超时
- string.c_str() -> 返回一个char* 指针
- fun_helper 需要加一个const，不然会通不过oj
- 其实可以改名
class Solution {
public:
bool isMatch(string s, string p) {
/*if(s == ""){
return false;
}*/
return isMatch(s.c_str(), p.c_str());
}
bool isMatch(const char* s, const char* p){
if(*s == '\0' && *p == '\0'){
return true;
}
if(*s != '\0' && *p == '\0'){
return false;
}
if(*(p + 1) == '*'){
if((*s != '\0' && *s == *p) || (*s != '\0' && *p == '.')){
return isMatch(s, p + 2) || // 不匹配
isMatch(s + 1, p + 2) || // 匹配一个
isMatch(s + 1, p); // 匹配多个
}else{
return isMatch(s, p + 2);
}
}
if(*s != '\0' && (*s == *p || *p == '.')){
return isMatch(s + 1, p + 1);
}
return false;
}
};
