LeetCode-Regular Expression Matching

Regular Expression Matching

##题目

####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

##解题思路
该题是对字符串进行正则表达式匹配，可以采用动态规划的方法进行求解。动态规划基本思想就是把我们计算过的历史信息记录下来，等到要用到的时候就直接使用，不用重新计算。
在这个题里面，假设我们维护一个布尔数组res[i+1][j+1],代表s的前i个字符和p的前j个字符是否匹配(注意这里res的维度是s.length()+1,p.length()+1)。以下主要分三种情况： 

1. p[j]不是'*'。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是'.',也是相同），并且res[i][j]==true，则res[i+1][j+1]也为true，否则res[i+1][j+1]=false; 
2. p[j]是'*'，但是p[j-1]!='.'。那么只要以下条件有一个满足即可对res[i+1][j+1]=true： 
    2.1 res[i+1][j]为真（'*'只取前面字符一次）; 
    2.2 res[i+1][j-1]为真（'*'前面字符一次都不取，也就是忽略这两个字符）; 
    2.3 res[i][j+1]=true && s[i]==s[i-1] && s[i-1]==p[j-1](这种情况是相当于i从0到s.length()扫过来，如果p[j]对应的字符是‘*’那就意味着接下来的串就可以依次匹配下来，如果下面的字符一直重复，并且就是‘*’前面的那个字符）。 
3. p[j]是'*'，并且p[j-1]=='.'。因为".*"可以匹配任意字符串，所以在前面的res[i+1][j-1]或者res[i+1][j]中只要有i+1是true，那么剩下的res[i+1][j+1],res[i+2][j+1],...,res[s.length()][j+1]就都是true了。

这道题有个很重要的点，就是实现的时候外层循环应该是p,然后待匹配串s内层循环扫过来。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    //res[i+1][j+1]结尾为是s[i]和p[j]
   public boolean isMatch(String s, String p) {  
        if(s.length()==0 && p.length()==0)  
            return true;  
        if(p.length()==0)  
            return false;  
        boolean[][] res = new boolean[s.length()+1][p.length()+1];  
        res[0][0] = true;  
        for(int j=0;j<p.length();j++)  
        {  
            if(p.charAt(j)=='*')  
            {  
                if(j>0 && res[0][j-1]) res[0][j+1]=true;  
                if(j<1) continue;  
                if(p.charAt(j-1)!='.')  
                {  
                    for(int i=0;i<s.length();i++)  
                    {  
                        if(res[i+1][j] || j>0&&res[i+1][j-1]   
                        || i>0 && j>0 && res[i][j+1]&&s.charAt(i)==s.charAt(i-1)&&s.charAt(i-1)==p.charAt(j-1))  
                            res[i+1][j+1] = true;  
                    }  
                }  
                else  
                {  
                    int i=0;  
                    while(j>0 && i<s.length() && !res[i+1][j-1] && !res[i+1][j])  
                        i++;  
                    for(;i<s.length();i++)  
                    {  
                        res[i+1][j+1] = true;  
                    }  
                }  
            }  
            else  
            {  
                for(int i=0;i<s.length();i++)  
                {  
                    if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')  
                        res[i+1][j+1] = res[i][j];  
                }  
            }  
        }  
        return res[s.length()][p.length()];  
    }  
}

Comments

▲