leetcode 正則匹配 今日遞歸解決，明日動(dòng)態(tài)規(guī)劃

struct Solution;

// 此時(shí)這個(gè)函數(shù)做的事情
// 第二個(gè)字符串不是* 此時(shí)是否相等 . 或者字符串相等
// 第二個(gè)字符是*號(hào)，匹配的話相等去掉匹配規(guī)則是否相等。

impl Solution {
    pub fn is_match_recursion(s: String, p: String) -> bool {
        if p.len() == 0 {
            return s.len() == 0;
        };
        let s_arr: Vec<char> = s.chars().collect();
        let p_arr: Vec<char> = p.chars().collect();
        let mut curMatch;

        if s_arr.len() == 0 {
            curMatch = false;
        } else {
            curMatch = s_arr[0] == p_arr[0] || p_arr[0] == '.';
        }

        if p_arr.len() > 1 && p_arr[1] == '*' {
            if curMatch {
                return Solution::is_match_recursion(s[1..].to_string(), p[..].to_string());
            } else {
                return Solution::is_match_recursion(s[..].to_string(), p[2..].to_string());
            }
        } else {
            if curMatch {
                return Solution::is_match_recursion(s[1..].to_string(), p[1..].to_string());
            } else {
                return false;
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_find_match() {
        assert_eq!(
            true,
            Solution::is_match_recursion(String::from("aa"), String::from("a*"))
        );
        assert_eq!(
            false,
            Solution::is_match_recursion(String::from("aa"), String::from("a"))
        );
        assert_eq!(
            true,
            Solution::is_match_recursion(String::from("ab"), String::from(".*"))
        );
        assert_eq!(
            true,
            Solution::is_match_recursion(String::from("aab"), String::from("c*a*b"))
        );
        assert_eq!(
            false,
            Solution::is_match_recursion(String::from("mississippi"), String::from("mis*is*p*."))
        );
    }
}