leetcode Regular Expression Matc
2019-12-19 本文已影响0人
奔跑的蛙牛
leetcode 正则匹配 今日递归解决,明日动态规划
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*."))
);
}
}