Problem
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).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
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 precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
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".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
Solution 1: Recursion
Time complexity: O((|s| + |p|) * 2 ^ (|s| + |p|))
Space complexity: O(|s| + |p|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua, 14 ms class Solution { public: bool isMatch(string s, string p) { return isMatch(s.c_str(), p.c_str()); } private: bool isMatch(const char* s, const char* p) { if (*p == '\0') return *s == '\0'; // normal case, e.g. 'a.b','aaa', 'a' if (p[1] != '*' || p[1] == '\0') { // no char to match if (*s == '\0') return false; if (*s == *p || *p == '.') return isMatch(s + 1, p + 1); else return false; } else { int i = -1; while (i == -1 || s[i] == p[0] || p[0] == '.') { if (isMatch(s + i + 1, p + 2)) return true; if (s[++i] == '\0') break; } return false; } return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment