10. Regular Expression Matching

http://blog.csdn.net/hk2291976/article/details/51165010

dp[i][j]的含义是s[0-i] 与 s[0-j]是否匹配。

1 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];
3If p.charAt(j) == ‘’:
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a only counts as empty
2 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
dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
dp[i][j] = dp[i][j-2] // in this case, a* counts as empty

class Solution
{
public:
    static const int FRONT=-1;
    bool isMatch(string s, string p)
    {
        int m = s.length(),n = p.length();
        bool dp[m+1][n+1];
        dp[0][0] = true;
//初始化第0行,除了[0][0]全为false，毋庸置疑，因为空串p只能匹配空串，其他都无能匹配
        for (int i = 1; i <= m; i++)
            dp[i][0] = false;
//初始化第0列，只有X*能匹配空串，如果有*，它的真值一定和p[0][j-2]的相同（略过它之前的符号）
        for (int j = 1; j <= n; j++)
            dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2];

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (p[j - 1] == '*')
                {
                    dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j];

                }
                else   //只有当前字符完全匹配，才有资格传递dp[i-1][j-1] 真值
                {
                    dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];

                }
            }
        }
        return dp[m][n];
    }
};