[leetcode]-10 Regular Expression Matching-蒲公英云

[leetcode]-10 Regular Expression Matching

描述：

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).

思路：

采用动态规划（Dynamic Programming）的思想，首先先介绍一下动态规划的概念，即把原问题分解成子问题进行求解。

两种不同的动态规划解决方案：

自上而下：你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（*Memoization*），其使用了递归计数。

自下而上：你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（*Tabulation，*table-filling algorithm**），其用到了迭代技术。

在本题中，我们使用一个动态规划矩阵dp[][]，原问题是dp[s.length-1][p.length]为true或者false，而若干个子问题为判断dp[i][j]。

我们给出问题之间的关系：

1, If p.charAt(j+1) == s.charAt(i+1) :  dp[i+1][j+1] = dp[i][j];
2, If p.charAt(j+1) == '.' : dp[i+1][j+1] = dp[i][j];
3, If p.charAt(j+1) == '*':
    here are two sub conditions:
           1   if p.charAt(j) != s.charAt(i+1) and p.charAt(j) != '.':
                        dp[i+1][j+1] = dp[i+1][j-1]  //in this case, a* only counts as empty
           2   if p.charAt(j) == s.charAt(i+1) or p.charAt(i) == '.':
                          dp[i+1][j+1] = dp[i][j+1]    //in this case, a* counts as multiple a
                       or dp[i+1][j+1] = dp[i+1][j]   // in this case, a* counts as single a
                       or dp[i+1][j+1] = dp[i+1][j-1]   // in this case, a* counts as empty

代码：

public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        int i = 0, j = 0;
        //initialize dp matrix
        dp[0][0] = true;
        for (i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
            }
        }
        //dp by iteration
        for(i = 0; i < s.length(); ++i){
            for(j = 0; j < p.length(); ++j) {
                if (s.charAt(i) == p.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j];
                } else if (p.charAt(j) == '.') {
                    dp[i+1][j+1] = dp[i][j];
                } else 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 - 1];
                    } else if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
                        dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j] || dp[i+1][j-1];
                    }
                }
            }
        }
        return dp[s.length()][p.length()] ;
    }