# 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:

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 *.

# 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, ‘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 = “cab”
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 = “misisp*.”
Output: false

# Solution

``````impl Solution {
pub fn check(mut s: &mut Vec<char>, p: &mut Vec<char>) -> bool {
if p.len() == 0 {
return s.len() == 0;
}

if p.len() == 1 {
return (s.len() == 1) && (s[0] == p[0] || p[0] == '.');
}

if p[1] != '*' {
if s.len() == 0 {
return false;
}

let mut s1 = s.clone();
let mut p1 = p.clone();
s1.remove(0);
p1.remove(0);

return (s[0] == p[0] || p[0] == '.') && Solution::check(&mut s1, &mut p1);
}

let mut p1 = p.clone();
p1.remove(0);
p1.remove(0);

while (s.len() != 0) && (s[0] == p[0] || p[0] == '.') {
let mut s1 = s.clone();
if Solution::check(&mut s1, &mut p1) {
return true;
}

s.remove(0);
}

return Solution::check(&mut s, &mut p1);
//return false;
}

pub fn is_match(s: String, p: String) -> bool {
let mut p: Vec<char> = p.chars().collect();
let mut s: Vec<char> = s.chars().collect();

return Solution::check(&mut s, &mut p);
}
}``````

(=￣ω￣=)··· 暂无内容！

169

36

219

81