README.md

010.正则表达式匹配

问题描述

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符。  
'*' 匹配零个或多个前面的元素。  

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解决方案

  这题是一个dp，状态设置为：dp[i,j]表示s[0,i)和p[0,j)的匹配情况。
  刚开始考虑这个问题会抓不到解决问题的线头，但是其实可以很明确的线索是，dp[i,j]的状态一定是受p[j-1]决定的，而p[j-1]的取值有两种情况，所以首先分两类讨论：

1、p[j-1]!='*'

  这种情况下p[j-1]的取值也是有两种情况的，一种是常规字符还有一种是万能字符'.'。因为涉及到的历史状态只有dp[i-1,j-1]，所以状态方程很好写：dp[i][j]= dp[i-1][j-1] && (p[j-1]==s[i-1] || p[j-1]=='.')。

2、p[j-1]=='*'

  这种状态看着复杂，但是其实也并不复杂，因为'*'的功能其实就是三种：匹配0次、匹配1次以及匹配多次。假定上述三种情况依次标序123，并假定当前s[i-1]记为字符c。

• 情况1：匹配0次的情况会发生在'*'前面的字符和c不匹配，即s[i-1]!=p[j-2]，状态转移变成了dp[i,j]=dp[i-1,j-2]；或者是1对多的情况，状态转移为dp[i,j]=dp[i,j-2]。

举例1：
s='abcde'
p='abcc*de'
dp[4,5]=dp[3,3]

举例2：
s='a'
p='ac*'
dp[1,3]=dp[1,1];

• 情况2：匹配1次的情况发生在c和'*'的前一个字符相等或者'*'的前一个字符为万能字符，即s[i-1]==p[j-2]或者p[j-2]=='.'，这个时候我们选择匹配1次，状态转移就是dp[i,j]=dp[i-1,j-1]。

举例：
s='abccd'
p='abc*d'
dp[4,4]=dp[3,3]

• 情况3：匹配多次的情况发生在c和'*'的前一个字符相等或者'*'的前一个字符为万能字符，且c已经出现多次，这个时候，选择匹配多次，然而状态转移的时候并不能确定此时'*'已经匹配了多少次，所以根据迭代的思想，假定它的n-1次匹配是成功的，那么状态转移就是dp[i,j]=dp[i-1,j]

举例：
s='baaaac'
p='ba*c'
dp[5,3]=dp[4,3]=dp[3,3]
再根据情况2
dp[3,3]=dp[2,2]

边界条件

  剩下的事情就是考虑边界条件，dp[0,0]表示s和p都是空串，必然匹配，所以dp[0,0]=true。除此之外p取空时均为false，即dp[i,0]=false。dp[0,i]的情况考虑也比较简单，如果有一个'*'就可以匹配前面的字符0次。

举例：
s=''
p='a*b*c*'
dp[0,6]=dp[0,2]=dp[0,0]=true

  所有的事情都考虑完了，下面是实现的代码：

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