010.md

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

思路：

 动态规划：
 由于p[1...i]和s[1...j]取决于p[1...i-1]和s[1...j-1]和p[i]和s[j]，这个子问题和原问题又是同一个问题。
 这里关键的地方是，总是去p的最后一个字符和s的最后一个字符去匹配。因为顺序处理的话 有这种情况：
 s = "abcdaef" p = "abcda*aef" 这种 形式，遇到s的第二个a的时候：p中的a*选择不匹配任何字符，则后面可以匹配成功，如果选择匹配一个a  则后边就不能匹配成功。这就需要回溯了。

 s和p前面分别垫上一个空字符。
 设bool e[i][j] 表示为p[1...i]是否能匹配s[1...j]。

 初始化e[0][0] = 1;空串匹配空串肯定为1.
 初始化第0行 e[0][j]=0 (j>0 && j<s.size())  
 初始化第0列 if(p[i]=='*' && e[i-2][0]==1) e[i][0]=1 else e[i][0] = 0
 p为*a这种形式也可以匹配空s
     找出递归式:
 p[i] != '*' 时：
    当 p[i] = s[j] 或者 p[i] = '.' 时 e[i][j] = e[i-1][j-1]
    当 p[i] != s[j] e[i][j] = false。 因为最后一个字符无法满足
 p[i] == '*'时,e[i][j]等于下面其中之一为true的值：

1. e[i-2][j]   //表示 x* 为空
   
2. e[i-1][j]    //表示 x* 只匹配了一个字符x。
   
3. e[i][j-1]   //匹配了 n>=2 个字符，同时还要满足 p[i-1] = s[j] || p[i-1] = '.'。
   //note: 如果p=".* "   s="asfdssd" 返回的是true，表示的是n个'.',n>=0。
    e的表示图为：纵坐标表示p,横坐标表示s。
   

代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;//使动态规划更好理解
        p = " " + p;
        int row_sz = p.size();
        int col_sz = s.size();
        
        bool e[row_sz][col_sz];//e[i][j] 表示p[0..i]能否用来匹配s[0..j]
        e[0][0] = 1;//p和s为空 肯定是true的。
        //初始化第一行，也就是p为空，肯定是false
        for(int j=1;j<col_sz;++j){
            e[0][j] = 0;
        }
        //初始化第一列，也就是s为空，如果p中有 字母* 这种情况则有可能为true
        for(int i=1;i<row_sz;++i){
            //进入if表示，字母*，这种形式为empty 即跳过。
            if(p[i]=='*') e[i][0] = e[i-2][0];//由于i=1时 p[i]不可能是*，所以保证了i-2不会出现小于0的情况。
            else e[i][0] = 0;
        }
        //i为p的索引 即为二维数组的行号
        for(int i=1;i<row_sz;++i){
            for( int j=1;j<col_sz;++j){
                //如果为. 或者最后的字符相同则true还是false取决于p[0..i-1] 和 s[0..j-1]
                if(p[i]==s[j] || p[i]=='.') e[i][j] =  e[i-1][j-1]; 
                else if(p[i]!='*'){ 
                // p[i]!='*' 且 p[i]==s[j] 那么肯定是false因为最后一个字符无法匹配
                    e[i][j] = 0;
                }
                else{ //p[i] == '*'，有三种情况，x* 完全不匹配，或者匹配一个字符，或者匹配大于等于2次。和.* 的情况。
                     e[i][j] = e[i-2][j] || e[i-1][j] || (e[i][j-1] && ('.' == p[i-1] || s[j]==p[i-1]));  
                                                                                        //^^^^^^^^^^^^与x* 中的x匹配成功，次数大于1次。
                }
            }
        }
       
        return e[row_sz-1][col_sz-1];
    }
};