10.Regular Expression Matching #

题目 #

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

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 (.)".

Constraints:

1 <= s.length <= 20
1 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

代码 #

impl Solution {

    pub fn is_match(s: String, p: String) -> bool {
        let mut f: [[bool; 32]; 22] = [[false; 32]; 22];

        f[0][0] = true;

        for j in 2..p.len() + 1{
            let b = p.chars().nth(j - 1).unwrap();

            if f[0][j - 2] && b == '*' {
                f[0][j] = true
            }
        }

        for i in 1..s.len() + 1 {
            for j in 1..p.len() + 1 {
                let a = s.chars().nth(i - 1).unwrap();
                let b = p.chars().nth(j - 1).unwrap();
                

                if f[i - 1][j - 1] && a == b {
                    f[i][j] = true
                }

                if i != s.len() + 1 && f[i - 1][j - 1] && b == '.' {
                    f[i][j] = true
                }

                if j < 2 || b != '*' {
                    continue;
                }

                let c = p.chars().nth(j - 2).unwrap();

                if f[i - 1][j] && a == c {
                    f[i][j] = true
                }

                if f[i - 1][j] && c == '.' {
                    f[i][j] = true
                }

                if f[i - 1][j - 2] && a == c {
                    f[i][j] = true
                }

                if f[i - 1][j - 2] && c == '.' {
                    f[i][j] = true
                }

                if f[i][j - 2] {
                    f[i][j] = true
                }

            }
        }

        return f[s.len()][p.len()];
    }
}