10. Regular Expression Matching (Facebook Hard)

题目

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("abc", ".*") → true
isMatch("aab", "c*a*b") → true

思路

'.' 匹配任意单字符，但不能匹配空字符；'' 可以匹配 0 或多个前面一个字符，匹配 0 个就是将前面的字符删掉，匹配多个代表对前面字符的重复。'' 也可以匹配前面的 '.' 即 '.*' 可以代表一个 '.' 两个 '.' 或者多个 '.' 每一步匹配都会出现多种条件判别情况，我们用递归和动态规划来分别实现。

题解1: Recursion

定义一个 isMatch 递归函数进行匹配，两个变量：s 和 p。先对 p 做条件判断，在此基础上，对 s 做条件判断。

条件

p.length() == 0, s 为空返回 true，s 不空则返回 false。
p.length() == 1
(2-1) s 为空返回 false；
(2-2) s 不为空，p.charAt(0) == s.charAt(0) 或者 p.charAt(0) == '.'
若满足则返回 isMatch(s.substring(1), p.substring(1))，否则为 false。
P.length() >= 2
(3-1) s 不空，p.charAt(1) != ''，且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' 时，若满足则返回 isMatch(s.substring(1), p.substring(1))，否则为 false。 (3-2) s 不空，P.length() >= 2 p.charAt(1) == ''，且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' 时，如果该字符只出现一次 if (isMatch(s, p.substring(2))) 返回 true，否则重复执行 s = s.substring(1) (3-3) p.charAt(1) == '*', 返回 isMatch(s, p.substring(2)). 由上述，我们把条件 2 的最后一种情况和条件 3 的第一种情况合并。

Time

O((m+n)x2^(m+n/2)), m=s.length,n=p.length

Space

O(m^2 + n^2)

代码如下：

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

题解2: DP

定义一个 boolean dp[i][j]，用来表示 s[0-i] 与 p[0-j] 是否匹配。dp[0][0] 表示两个空字符串是否匹配，初始化为 true。dp[i][j] 为 true 的条件如下：

条件

s.charAt(i)=p.charAt(j)
p.charAt(j)='.'
p.charAt(j)='*'
(3-1) if p.charAt(j-1)!=s.charAt(i)， * matches zero of the preceding element. (3-2) if p.charAt(j-1)==s.charAt(i)，或者 p.charAt(j-1) '.' * Matches one or more of the preceding element

注意⚠

如右图所示，考虑到这种情况("aab", "cab")中，c* 应匹配为空字符串，接下来应尝试匹配 aab 和 a*b。这个子问题的解决应从对应空字符串的匹配开始，即 dp[0][2] 应设为 true。

Time

O(mn),m=s.length,n=p.length

Space

O(mn)

代码如下：

class Solution {
  public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    boolean[][]dp=new boolean[s.length()+1][p.length()+1];
    dp[0][0]= true;
    for(int i=0;i<p.length();i++){  
        if(p.charAt(i)=='*'&& dp[0][i-1])
            dp[0][i+1]=true;
    }
    for(int i=0;i<s.length();i++){  
        for(int j=0;j<p.length();j++ ){  
            if(p.charAt(j)=='.'){  
                dp[i+1][j+1]=dp[i][j];
            }
            if(p.charAt(j)==s.charAt(i)){  
                dp[i+1][j+1]=dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                }
                else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
  }
}