leetcode: Regular Expression Matching

问题描述：

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

原问题链接：https://leetcode.com/problems/regular-expression-matching/

 

问题分析

    这个问题相对来说比较复杂，要找到一个合理快速的思路确实不容易。我们可以从简单到复杂的过程来一步步推导。对于正则表达式匹配来说，在没有特殊字符要求匹配的情况下，我们针对源字符串s, 模式字符串p两个字符串来说，它们就是互相比对两边的字符，看它们是否相同。如果一直比较到最后发现两边的长度相同，则表示它们是匹配的。这是纯字符匹配的情况。几乎大家都能想到。

    现在我们按照前面的问题再稍微接近一点，如果考虑字符'.'的情况，在具体的判断里就需要额外增加一个判断对于模式字符是该字符的情况。相对来说，用递归的方式来描述这种简化情况的代码如下：

 

public boolean match(String s, String p, int i, int j) {
	if(j == p.length()) return i == s.length();
	if(i < s.length() && j < p.length()) {
		if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')
			return match(s, p, i + 1, j + 1);
		else
			return false;
	}
	return false;
}

    上述是仅仅针对模式串中含有普通字符和'.'字符的情况。如果这个时候再进一步考虑可以匹配多个字符的'*'号，该怎么来处理呢？

    按照前面的描述，一个*表示匹配0到多个它前面的那个元素。所以我们可以针对它匹配的情况展开讨论一下。比如有串s “abc”, p "c*abc"，针对这种情况，要想满足两边的匹配，p里的*号应该是匹配前面0个字符。也就是不匹配前面的那个字符c。当然，还有匹配1到多个的情况，比如s "aaabc", p "a*bc"，这个时候'*'号前面的字符a和s串里对应目标的连续多个字符a都可以匹配。因此针对这种情况我们需要针对这种情况每种都要递归比较。因为我们这里是要寻找它的匹配，所以针对这多种情况只要某一种匹配，我们就应该选择那一种。

    有了前面的这些讨论，我们好像有了一点思路。假设针对字符串s, p来说，当前它们比较的位置分别为i, j。当s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'而且p.charAt(j+1) != '*'，这个时候好办，我们接着比较下一个。相当于递归的去比较下一个，也就是i+1, j + 1。嗯，这是一种场景的递归方式。而如果在p.charAt(j+1) != '*'的条件下s.charAt(i) != p.charAt(j) && p.charAt(j) != '.'的时候，这就是一个普通字符不匹配的情况，我们需要直接返回false。

    另外一个场景就是如果p.charAt(j+1) == '*'。因为有'*'号的存在。我们需要对s字符串的i, i + 1...等位置的字符和p的i位置进行比较。而到底是要到s的哪个字符为止呢？这就是要满足s.charAt(i) == p.charAt(j)这个条件了。因为在i以及i后面可能有多个和p的j位置字符相等的。所以这里需要用一个循环以s.charAt(i) == p.charAt(j)作为判断条件。当它们相等的时候，我们就有了一个递归的情况，也就是match(s, p, i, j +2)。这种关系用伪码表示就是：

 

 while(s.charAt(i) == p.charAt(j)) {
    if(match(s, p, i, j + 2)) return true;
    i++;
}

 

    根据上述的讨论，我们已经差不多把大部分的细节定下来了。当然还有一个需要考虑的地方就是在递归的过程中判断i, j的长度，防止它们超过对应字符串的长度。结合这个条件，我们把各种场景来详细的列一下：

•  当p中间j后面的字符不是'*'号时它的条件应该是j < p.length() - 1 && p.charAt(j + 1) != '*'。当然，这个条件还忽略了一种情况，就是j == p.ength() - 1，这个时候j已经是p字符串的最后一个，它肯定不会有后面的字符了也就不存在它后面的字符为星号的情况。把这两种情况综合起来表示，可以概括成j == p.length() - 1 || p.charAt(j + 1) != '*'。为什么这种条件可以表现得这么简短呢？编程语言里条件判断的短路规则，这里就是这种方式的应用。有了这个条件之后，这个条件里该是些什么内容呢？因为保证了p后面的不是星号，所以只需要判断i, j两个位置的字符是否相等。当然，还要加上一个附加条件，就是保证j不越界。所以这部分代码可以表示成如下： 

if(j == p.length() - 1 || p.charAt(j + 1) != '*') {
	if(i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')) {
		return match(s, p, i + 1, j + 1);
	} else
		return false;
}

 

•  当p当前字符后面确实是星号的时候，则需要针对每种匹配进行递归，在前面的讨论里还要针对p的当前位置是'.'而后续元素是星号的情况，因此其细化后的这部分代码如下：

 

while(i < s.length() && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))) {
    if(match(s, p, i, j + 2)) return true;
    i++;
}

 

    那么，这几种情况讨论完了就整个结束了吗？上述循环是针对s的若干个元素和p的j位置元素的匹配比较。如果上述的所有比较都不匹配呢？也就是说上述的while循环里没有找到匹配的。这个时候我们就需要继续递归比较后续的部分。所以后面还需要返回一个match(s, p, i, j + 2)。

    综合起来，上述的代码片段可以整合成如下的一段代码：

 

public class Solution {
    public boolean isMatch(String s, String p) {
        return match(s, p, 0, 0);
    }
    
    public boolean match(String s, String p, int i, int j) {
        if(j == p.length()) return i == s.length();
        if(j == p.length() - 1 || p.charAt(j + 1) != '*') {
            return (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')) && match(s, p, i + 1, j + 1);
        }
        while(i < s.length() && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))) {
            if(match(s, p, i, j + 2)) return true;
            i++;
        }
        return match(s, p, i, j + 2);
    }
}

    概括起来说，上述方法的思路就是首先根据当前模式串p所在的位置j判断 j+1是否为*，如果不是则按照普通的字符匹配来递归，否则根据s在i到i+k的位置和p的j的位置进行递归比较。其中i到i+k的位置的字符和p中间j位置相等。

 

动态规划法改进

    上述的递归解法在于针对p串中当前元素的后面一个元素是否为星号来判断。当不是星号的时候进行普通字符串匹配的判断，根据判断结果来决定是否下一步的递归。如果是星号则要进行多个字符匹配情况的判断递归。但是上述的方法有一个问题，就是递归的的穷举式计算法在最坏的情况下其时间复杂度可能达到一个指数级别的。而上述的很多递归判断条件里给了我们一个提示。就是它们很多的递归的运算是重复计算的。这就给了我们一个信号，就是很多重复计算的东西是可以避免的。

    在动态规划的方法里，它们本身就是根据一些递归描述的问题，将一些子问题的计算结果保存起来，这样以后每次的运算就不用再重复的去计算，而只需要去直接取中间的结果就可以了。这种方式能够带来很大效率上的提升。那么针对这个问题该怎么去运用动态规划的思路呢？

    我们可以定义一个boolean dp[s.length() + 1][p.length() + 1]的二维数组。数组dp[i][j]表示对应s的前i个元素和p的前j个元素是否匹配。而这里为什么要声明成一个比两个数组长度都大一的二维数组呢？因为我们利用动态规划方法是一层层的递推过来的。dp[0][0]表示对应s的前面0个元素和p的前面0个元素。我们可以认为它们是匹配的。而对于dp[0][j]和dp[i][0]分别表示两个串中一个参与比较的是0个字符。所以对于i, j > 1的情况，它们的初始结果设定为不匹配的。在忽略其他节点的情况下，它们就预先构造成了一个如下图的矩阵：

 

     这里t表示true, f表示false。我们要求得的最终答案就是要返回dp[s.length()][p.length()]。有了这么一个基础，对于这个矩阵里的元素该怎么推导呢？我们结合前面的情况来详细讨论一下。

     对于参与比较的i, j两个节点，它们对应s, p的位置分别是s.charAt(i - 1), p.charAt(j - 1)。因为对应矩阵里的i, j，它们表示对应串中的前i, j个元素，对应的索引从0开始，所以要减一。当我们取到p.charAt(j - 1) != '*'的时候，我们仅仅考虑普通的匹配情况，只需要看它们前面的i - 1, j - 1是否匹配。然后就取决于当前的s.charAt(i) == p.charAt(j)。当然，考虑到p里的单字符匹配符号'.'，我们总体的匹配表达式应该是:

dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')。

   上面是针对当前字符不是星号的情况。如果当前字符是星号呢？又该怎么来推导呢？当碰到p当前的字符是星号时，它其实对应有两种情况，一种是实际上s中的字符和p中间的星号以及之前的字符是0个匹配，也就是不匹配。这个时候就要看s在i这个位置的字符和p在j这个位置之前两个的那个字符这两段是否匹配。也就是条件：dp[i][j - 2]。

    另外一个条件就是实际上匹配了一个或者多个字符。既然至少总要匹配一个字符，那么s中间到i位置的字符串应该和p中间到j之前的那个字符串应该匹配。当然也有p中间j之前的那个元素是'.'符号的情况。这种情况用代码概括起来就是：dp[i - 1][j] && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))

    根据上述的讨论，我们可以得到如下的代码实现：

 

public class Solution {
    public boolean isMatch(String s, String p) {
        int sl = s.length(), pl = p.length();

        boolean[][] dp = new boolean[sl + 1][pl + 1];
        dp[0][0] = true; 

        for(int i = 0; i <= sl; i++) {
            for(int j = 1; j <= pl; j++) {
                char c = p.charAt(j-1);
                if(c != '*') {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (c == '.' || c == s.charAt(i - 1));
                } else {
                    dp[i][j] = (j > 1 && dp[i][j - 2]) ||
                        (i > 0 && dp[i - 1][j] && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)));
                }
            }
        }
        return dp[sl][pl];
    }
}

    上述代码使用了一个二维数组，然后通过遍历推导得到最终的结果，其空间复杂度为O(N * N)，时间复杂度也是O(N * N)。上述代码里有一个值得注意的细节就是，每次我们判断当前dp[i][j]的值的时候，因为它的结果是一步步递推过来的，所以需要根据情况同时去考虑dp[i-1][j-1]或者dp[i-1][j]等情况。

 

总结

    正则表达式的字符串匹配是一个比较复杂的问题。它的难点在于针对多种情况的递归关系，再结合一些数组访问边界控制的情况，很容易让人焦头烂额。在具体的问题推导中，可以结合一些简单的情况再一步步的推导到一些复杂点的场景。 

 

参考材料

 http://blog.csdn.net/linhuanmars/article/details/21145563

 http://articles.leetcode.com/regular-expression-matching

 https://leetcode.com/discuss/66032/java-solution-o-n-2-dp-with-some-explanations

https://leetcode.com/discuss/75098/java-4ms-dp-solution-with-o-n-2-time-and-o-n-space-beats-95%25