LeetCode #10 Regular Expression

3.LeetCode#10 Regular Expression Matching

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

动态规划求解

分析题意可知，判断当前字符串字符与匹配符是否匹配需要考虑前一个字符的匹配情况，因此想到可以采用动态规划求解。
我们使用dp[i][j]代表字符串A第i个字符与匹配符B第j个字符的匹配情况,有如下可能：

• A[i] == B[j] || B[j] == '.'
  • 在此情况下我们可以知道：
    dp[i][j] = dp[i - 1][j - 1]
• B[j] == '*' 此时匹配符为星号，说明其前面的字符可出现多次或0次，因此需要继续分类：
  • B[j-2] != A[i - 1] && B[j - 2] != '.'时：
    dp[i][j] = dp[i][j-2] //a*匹配0次
  • B[j-2] != A[i - 1] || B[j - 2] != '.'时:
    dp[i][j] = dp[i][j-2] // a*匹配0次
dp[i][j] = dp[i][j-1] // a*匹配1次
dp[i][j] = dp[i-1][j] // a*匹配多次

综上，代码如下:

public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();
         boolean[][] dp = new boolean[str.length + 1][pattern.length + 1];
        dp[0][0] = true;
        for (int i = 1; i < dp[0].length; i ++) {
            if(pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2];
        }
        for (int i = 1; i < dp.length; i ++) {
            for (int j = 1; j < dp[0].length; j ++) {
                if(pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]) dp[i][j] = dp[i - 1][j - 1];
                else if(pattern[j - 1] == '*') {
                    if(pattern[j - 2] != str[i - 1] && pattern[j - 2] != '.') dp[i][j] = dp[i][j - 2];
                    else dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                }
            }
        }
        return dp[str.length][pattern.length];
    }