1
2
3

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

1
2
3

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

1
2
3

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    /*
    * ## 解题思路
    * - 递归
    * 1. f(s, p): 表示s, p匹配情况；
    * 2. 如果p为空，则是否匹配取决于s也是否为空；
    * 3. 否则，p中存在3类字符: 普通字母, '.', '*';
    * 4. 对于普通字母或'.',
    *    f(s,p) = (p[0] == '.' || p[0] == s[0]) && f(s[1:], p[1:])
    * 5. 对于'*'字符，和前一个字符组成一个匹配单位，可以匹配0次或多次
    *    如果匹配了0次，则p前2个字符忽略, 使用p后续[2:]的来匹配s:
    *           f(s,p) = f(s, p[2:])
    *    或者匹配多次，则可先匹配第一个字符，再重新用p匹配后续的s[1:]:
    *           f(s,p)  = match(s[0], p[0]) && f(s[1:], p)
    */
    bool isMatch(string s, string p) {
        // 如果p为空，
        if (p.length() == 0) {
            return s.length() == 0;
        }
        // 第一个字符是否匹配
        bool is1stCharMatch = s.length() > 0 && (p[0] == s[0] || p[0] == '.');
        //a*匹配的情况
        if (p.length() >= 2 && p[1] == '*') {
            return isMatch(s, p.substr(2))   //x* 匹配了0个，则检查f(s, p[2:])
                || (is1stCharMatch && isMatch(s.substr(1), p));  //x*匹配多个，拆分为1个和
        } else { //非'a*'
            return is1stCharMatch && isMatch(s.substr(1), p.substr(1));
        }
    }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 两种方法:
    /// 1. 递归
    /// 2. 动态规划
    pub fn is_match(s: String, p: String) -> bool {
        /// - 递归
        /// 1. 模式字符串p中包含以下三种类型的字符: 普通字符，'.', '*';
        /// 2. 对于p,总共可分为以下几种形式:
        ///     a. p为空, 则取决于s是否也为空;
        ///     b. p以.*开头或a*开头(a相等), 则s的开头部分已经匹配, 需要继续匹配s除开首字符后部分和p是否匹配;
        ///     c. p以a*开头字符不同, 那么*代表0次匹配前面字符, 则p去掉a*部分, 剩下部分和s继续匹配；
        ///     d. p以.或x且x相匹配, 则需要看s和p剩下的部分subs, subp是否匹配;
        ///     e. 其他情况都不匹配;
        fn _is_match_rec(s: &[u8], p: &[u8]) -> bool {
            match (p, s) {
                // p为空
                ([], _) => s.is_empty(),
                // p: a*匹配
                ([a, b'*', ..], _) => {
                    _is_match_rec(s, &p[2..])
                        || (s.len() > 0 && (*a == b'.' || *a == s[0]) && _is_match_rec(&s[1..], p))
                }
                // p: .匹配
                ([b'.', ..], [_, ..]) => _is_match_rec(&s[1..], &p[1..]),
                // p: 普通字符匹配
                ([a, ..], [b, ..]) => a == b && _is_match_rec(&s[1..], &p[1..]),
                //其他情况
                _ => false,
            }
        }

        /// - 动态规划
        /// 1. 令 dp[i][j]: s[..i] 和 p[..j]是否匹配;
        /// 2. 目标: dp[s.len()][p.len()]
        /// 3. 递推关系:
        ///     dp[i+1][j+1] =
        ///         ( p[j] == '.' && dp[i][j] )
        ///      || ( p[j] == s[i] && dp[i][j] )
        ///      || ( p[j] == '*' && ( dp[i+1][j-1]
        ///                            || ( (p[j-1] == '.' || p[j-1] == s[i]) && dp[i][j+1] )
        ///                          )
        ///         )
        /// 4. 初始条件:
        ///     dp[0][0] = true, (s, p均为空)
        ///     dp[0][i+1] = p[i] == '*' && dp[0][i-1], (s为空)
        fn _is_match_dp(s: &[u8], p: &[u8]) -> bool {
            let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];

            //s为空,p为空
            dp[0][0] = true;
            for j in 0..p.len() {
                if j > 0 {
                    //s为空, p不为空
                    dp[0][j + 1] = p[j] == b'*' && dp[0][j - 1];
                }
                for i in 0..s.len() {
                    dp[i + 1][j + 1] = match p[j] {
                        b'.' => dp[i][j],
                        b'*' => {
                            dp[i + 1][j - 1] //*匹配0次
                                || ((p[j - 1] == b'.' || p[j - 1] == s[i]) && dp[i][j + 1])
                            //*匹配1或多次
                        }
                        a => dp[i][j] && s[i] == a,
                    };
                }
            }

            dp[s.len()][p.len()]
        }

        //_is_match_rec(s.as_bytes(), p.as_bytes())
        _is_match_dp(s.as_bytes(), p.as_bytes())
    }
}

// @lc code=end
//
struct Solution;

#[cfg(test)]
pub mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
        assert_eq!(Solution::is_match("aa".to_string(), "a*".to_string()), true);
        assert_eq!(
            Solution::is_match("aaa".to_string(), "a*a".to_string()),
            true
        );
        assert_eq!(
            Solution::is_match("mississippi".to_string(), "mis*is*p*.".to_string()),
            false
        );
        assert_eq!(
            Solution::is_match(
                "aabcbcbcaccbcaabc".to_string(),
                ".*a*aa*.*b*.c*.*a*".to_string()
            ),
            true
        );
    }
}