正则表达式匹配

正则表达式匹配

给你一个字符串 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

方法一：回溯

public boolean isMatch(String s, String p) {
    if (p.isEmpty()) {
        return s.isEmpty();
    }
    boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
    if (1 < p.length() && p.charAt(1) == '*') {
        return isMatch(s, p.substring(2))//跳过与*前面的字符比较，即认为出现次数为0
            || firstMatch && isMatch(s.substring(1), p);
    } else {
        return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

方法二：备忘录法（避免重复计算）
dp[i][j]表示s[i:],p[j:]能否匹配
时间复杂度O(TP)    用 T 和 P 分别表示匹配串和模式串的长度

public boolean isMatch(String s, String p) {
    int[][] dp=new int[s.length()+1][p.length()+1];//0：默认  -1：不匹配  1：匹配
    return helper(s,p,dp,0,0);
}

public boolean helper(String s,String p,int[][] dp,int i,int j){
    if (p.isEmpty()) {
        return s.isEmpty();
    }
    if(dp[i][j]!=0){
        return dp[i][j]==1;
    }
    boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
    boolean ans;
    if (1 < p.length() && p.charAt(1) == '*') {
        ans= helper(s, p.substring(2),dp,i,j+2)//跳过与*前面的字符比较，即认为出现次数为0
            || firstMatch && helper(s.substring(1), p,dp,i+1,j);
    } else {
        ans= firstMatch && helper(s.substring(1), p.substring(1),dp,i+1,j+1);
    }
    if(ans){
        dp[i][j]=1;
    } else {
        dp[i][j]=-1;
    }
    return ans;
}

方法三：动态规划(自底向上）

public boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[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--) {
            boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                dp[i][j] = dp[i][j + 2] || firstMatch && dp[i + 1][j];
            } else {
                dp[i][j] = firstMatch && dp[i+1][j+1];
            }
        }
    }
    return dp[0][0];
}

第二次做

递归

public boolean isMatch(String s, String p) {
    return isMatch(s, p, 0, 0);
}

public boolean isMatch(String s, String p, int i, int j) {
    if (j == p.length()) {
        return i == s.length();
    }
    boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
        return firstMatch && isMatch(s, p, i + 1, j) || isMatch(s, p, i, j + 2);
    }
    return firstMatch && isMatch(s, p, i + 1, j + 1);
}

备忘录

public boolean isMatch(String s, String p) {
    return isMatch(s, p, 0, 0, new int[s.length() + 1][p.length() + 1]);
}

public boolean isMatch(String s, String p, int i, int j, int[][] dp) {
    if (j == p.length()) {
        return i == s.length();
    }
    if (dp[i][j] != 0) {
        return dp[i][j] == 1;
    }
    boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
    boolean isMatch;
    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
        isMatch = firstMatch && isMatch(s, p, i + 1, j, dp) || isMatch(s, p, i, j + 2, dp);
    } else {
        isMatch = firstMatch && isMatch(s, p, i + 1, j + 1, dp);
    }
    dp[i][j] = isMatch ? 1 : -1;
    return isMatch;
}

动态规划

• s(i)=p(j)||p(j)='.' dp[i][j]=dp[i-1][j-1]
• p(j)='*' & s(i)!=p(j-1) dp[i][j]=dp[i][j-2]
• p(j)='*' & (s(i)==p(j-1)||p(j-1)='.') dp[i][j]=dp[i][j-2] || dp[i-1][j]
• 其它 dp[i][j]=false

注意初始值：

• dp[0][0]=true，表示都为空时相等
• p(j)='*'，可能与空串匹配，dp[0][j]=dp[0][j-2]

public boolean isMatch(String s, String p) {
    int len1 = s.length();
    int len2 = p.length();
    boolean[][] dp = new boolean[len1 + 1][len2 + 1];
    dp[0][0] = true;
    for (int i = 1; i < len2; i++) {
        if (p.charAt(i) == '*') {
            dp[0][i + 1] = dp[0][i - 1];
        }
    }
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            char c1 = s.charAt(i);
            char c2 = p.charAt(j);
            if (c1 == c2 || c2 == '.') {
                dp[i + 1][j + 1] = dp[i][j];
            } else if (c2 == '*') {
                if (c1 == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i][j + 1];
                } else {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1];
                }
            }
        }
    }
    return dp[len1][len2];
}