正则表达式匹配算法题解C/C++/JAVA/Python
  • 2019-12-22 14:34
  • 97
  • 0
  • 算法题解

题目:

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符,'*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。

p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

示例 1:

输入:s = "aa",p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa",p = "a*"

输出: true

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

示例 3:

输入:s = "ab",p = ".*"

输出: true

解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:s = "aab",p = "c*a*b"

输出: true

解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:s = "mississippi",p = "mis*is*p*."

输出: false

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/regular-expression-matching

C解法:

bool isMatch(char *s, char *p)
{
    bool dp[strlen(s) + 1][strlen(p) + 1];
    dp[strlen(s)][strlen(p)] = true;
    for (int i = strlen(s); i >= 0; i--)
    {
        for (int j = strlen(p) - 1; j >= 0; j--)
        {
            bool match = i < strlen(s) && s[i] == p[j] || p[j] == '.';
            if (j + 1 < strlen(p) && p[j + 1] == '*')
            {
                dp[i][j] = dp[i][j + 2] || (match && dp[i + 1][j]);
            }
            else
            {
                dp[i][j] = match && dp[i + 1][j + 1];
            }
        }
    }
    return dp[0][0];
}

C++解法:

class Solution
{
public:
    bool isMatch(string s, string p)
    {
        bool dp[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;
        for (int i = s.length(); i >= 0; i--)
        {
            for (int j = p.length() - 1; j >= 0; j--)
            {
                bool match = (i < s.length() && (s[i] == p[j] || p[j] == '.'));
                if (j + 1 < p.length() && p[j + 1] == '*')
                {
                    dp[i][j] = dp[i][j + 2] || match && dp[i + 1][j];
                }
                else
                {
                    dp[i][j] = match && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
};

JAVA解法:

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean first_match = (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        if (p.length() >= 2 && p.charAt(1) == '*') {
            return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
        } else {
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
    }
}

Python3解法:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        first_match = bool(s) and p[0] in {s[0], "."}
        if len(p) >= 2 and p[1] == "*":
            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
        else:
            return first_match and self.isMatch(s[1:], p[1:])
共 0 条评论