leetcode10 Regular Expression Matching 使用动态规划DP 代码详解

题目：

大致意思是实现一个两个字串的正则匹配，'.'可以代表任何字母，‘*’表示它之前的字母重复0到多次。

例如 a*可以是aaa或者是a或者为空等等。

实现代码：

class Solution {
    public boolean isMatch(String s, String p) {
    if (s == null || p == null) {     //s或p为空则无解
        return false;
    }
    boolean[][] dp = new boolean[s.length()+1][p.length()+1];  //java中初始化默认为false
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {   /*为了消除a*这种与空串的匹配，比如s是空，a*或者a*b*都是满足条件的，执行这个循环就可以得到满足条件的情况，并设为true*/
        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] || dp[i][j+1] || dp[i+1][j-1]);
                } else {
                    dp[i+1][j+1] =  dp[i+1][j-1];
                }           
            }
        }
    }
    return dp[s.length()][p.length()];
    }
}

主要算法思想：利用动态规划，建立一张表，每一个格代表当前是否可以匹配。其中的逻辑主要如下；

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
               if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
               else : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty

例如这样的一张表（p为a*b, s为aaab）：

	0	a	*	b
0	T	F	T	F
a	F	T	T	F
a	F	F	T	F
a	F	F	T	F
b	F	F	F	T

举例：

[0,0]格表示s和p都为空，这个时候为true；[1,1]表示的含义就是p为a，s为a时是否成立；[1,2]表示p为a*，s为a时是否可以成立。

代码解释：

第一个for循环，主要是为了找出类似p为x*或x*y*这样的字串与s空串的匹配。满足这样的条件应该为true。

之后二重循环，就是利用上述的规则，进行填表的过程。

leetcode10 Regular Expression Matching 使用动态规划DP 代码详解

相关推荐