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);
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接