leetcode Regular Expression Matching [rust]

leetcode 正则匹配 今日递归解决，明日动态规划

代码语言：javascript复制

struct Solution;

// 此时这个函数做的事情
// 第二个字符串不是* 此时是否相等 . 或者字符串相等
// 第二个字符是*号，匹配的话相等去掉匹配规则是否相等。

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*."))
        );
    }
}

leetcode 递归 动态规划

0 人点赞