0%

Leetcode010 Regular Expression Matching

Posted on Edited on In Valine:

Problem:

Given an input string (s) and a pattern (p), 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).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or .
Example 1:
Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:
Input:
s = “aa”
p = “a“
Output: true
Explanation: ‘‘ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:
Input:
s = “ab”
p = “.“
Output: true
Explanation: “.*” means “zero or more (*) of any character (.)”.
Example 4:

Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.
Example 5:

Input:
s = “mississippi”
p = “misis*p.”
Output: false

Intuition（Recursion）:

这一题难度较大，先考虑用递归的思路来解。本题是要求用正则表达式对字符串进行匹配，那么我们就按从左到右的顺序依次扫描，进行匹配。这个时候难点来了，如何处理.和*这两个正则表达式特有字符。

.好理解，能够对任意字符进行匹配。*则是能够让前面的字符出现任意次。这个任意次放到递归里面表达就可以等价看成忽略正则表达式的前面一个字符再与被匹配字符串进行一次匹配。第一种情况放到代码中实际就是被匹配字符串不动，正则表达式下标右移两格，其中移两格而不是一格的原因是要包括星号（isMatch(text, pattern.substring(2))）。

第二种情况就是被匹配表达式右移一格，正则表达式不动(first_match && isMatch(text.substring(1), pattern))。我们可以看到第二种情况不只包括*号前面的字符c出现一次的情况，也能包含c出现任意次的情况。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
public static boolean isMatch(String text, String pattern) {
    if (pattern.isEmpty()) return text.isEmpty();
    boolean first_match = (!text.isEmpty() &&
            (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

    if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
        return (isMatch(text, pattern.substring(2)) ||
                (first_match && isMatch(text.substring(1), pattern)));
    } else {
        return first_match && isMatch(text.substring(1), pattern.substring(1));
    }
}

Intuition（dynamic programming）:

先贴一个讲dynamic programming讲的还可以的链接：https://blog.csdn.net/u013309870/article/details/75193592

所谓dynamic programming,核心也就是要记住自己已经求解过的解。放到本题中，整体思路就是通过dp[i-][j-]来生成dp[s.length][p.length].其中s表示的是被测试字符串，p表示的是正则表达式。i表示的是被测试字符串当前匹配到的下标，j表示的是正则表达式的当前下标。

我们可以看到如果不考虑号，dp[i][j]如果要和dp[i-1][j-1]建立联系其实很简单。只要s[i-1]和p[j-1]一样或者p[j-1]是可以匹配任意字符的.就行了。整个二维矩阵的第一列我们也很清楚，如果被匹配字符串的长度为0，你正则表达式只要不为空，随便匹配啥都应该是false。第一行同理，那么这个时候我们就先生成了一个不考虑正则表达式带号的二维矩阵。

接下来的考验就是加入号后研究整个矩阵的变化。如果正则表达式出现号（出现在j-1的地方），那么要知道dp[i][j]能够为true(成功匹配)，只要满足dp[i][j-2]为true或者dp[i-1][j]为true。其中逻辑在上面讲递归逻辑的时候已经做了详细说明。这些工作都做完后，只需要放到for循环中进行遍历题目就出来了。最后说明一下为什么判断条件里面是p.charAt(j-1)而不是p.charAt(j).因为p.charAt(j-1)表示的是正则表达式的第j个字符而不是第j-1个字符，也就是二维数组中第二维的内容。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isMatch(String s, String p) {
     boolean[][] dp = new boolean[s.length()+1][p.length()+1];
     dp[0][0] = true;
     for (int i=0;i<=s.length();i++) { // i == 0 to fill up i=0 column. in order to handle s="", p="x*"
         for (int j=1;j<=p.length();j++) {
             if (j-1 >= 0 && p.charAt(j-1) == '*') {
                 boolean firstMatch = i > 0 && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.');
                 dp[i][j] = firstMatch && dp[i-1][j] || dp[i][j-2];
             } else {
                 boolean firstMatch = i > 0 && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.');
                 dp[i][j] = firstMatch && dp[i-1][j-1];
             }
         }
     }
     return dp[s.length()][p.length()];
 }