Regular Expression Matching

Description

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa", "a") → false
isMatch("aa", "aa") → true
isMatch("aaa", "aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Tags: String, Dynamic Programming, Backtracking

思路0

题意是让让你从判断s字符串是否正则匹配于p，这道题和Wildcard Matching很是相似，区别在于*，通配符的*是可以随意出现的，跟前面字符没有任何关系，其作用是可以表示任意字符串；而正则匹配的*不能单独存在，前面必须具有一个字符，其意义是表明前面的这个字符个数可以是任意个数，包括0个。首先我们用递归的方式来实现，其思路如下：

• 如果s和p都为空，那么返回true
• 如果p的长度为1，当s的长度也为1，并且他们首位匹配则返回true，否则返回false
• 如果p的第二个字符不为'*'，如果s为空，那就返回false，首位匹配则返回递归调用他们去掉首位的子字符串，否则返回false
• 如果p的第二个字符为'*'，循环当s不为空，且首位匹配，如果递归调用是否匹配s字符串和p去掉前两位的子字符串，则返回true，否则s去掉首字母继续循环
• 返回递归调用s字符串和p去掉前两位的子字符串是否匹配

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        if (p.length() == 1) {
            return s.length() == 1 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
        }
        if (p.charAt(1) != '*') {
            if (s.isEmpty()) return false;
            return (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')
                    && isMatch(s.substring(1), p.substring(1));
        }
        // match 1 or more preceding element
        while (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
            if (isMatch(s, p.substring(2))) return true;
            s = s.substring(1);
        }
        // match 0 preceding element
        return isMatch(s, p.substring(2));
    }
}

思路1

我们可以把上面的思路更简单化，如下

• 如果s和p都为空，那么返回true
• 如果p的第二个字符为*，由于*前面的字符个数可以为任意，那么我们先递归调用个数为0的情况；或者当s不为空，如果他们的首字母匹配，那么我们就递归调用去掉去掉首字母的s和完整的p
• 如果p的第二个字符不为*，那么我们就老老实实判断第一个字符是否匹配并且递归调用他们去掉首位的子字符串

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

思路2

另一种思路就是动态规划了，我们定义dp[i][j]的真假来表示s[0..i)是否匹配p[0..j)，通过思路1，我们可以确定其状态转移方程如下所示：

• 如果p[j - 1] == '*', dp[i][j] = dp[i][j - 2] || (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') && dp[i - 1][j];
• 如果p[j - 1] != '*'，dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]);

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

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：awesome-java-leetcode