010.Regular-Expression-Matching

此题带有很明显的DP解法的特征，dp[i][j]就代表s[1..i]和p[1...j]的字符串是否匹配。（以1-index为起点）

我们逐个分析一下：

1.如果p[j]是字母，那么s[i]必须是与其相同的字母才行。所以写成表达式 dp[i][j] = (s[i]==p[j] && dp[i-1][j-1])

2.如果p[j]是'.'，那么s[i]可以是任意字母。所以写成表达式 dp[i][j] = dp[i-1][j-1]

3.如果p[j]是'*'，那么星号的作用有两种情况。

第一种可以认为是重复0次，即考虑s[1..i]和p[1..j-2]是否匹配。那么记录 prob1 = dp[i][j-2]

第二种可以认为是重复了若干次。不管重复了几次，都要求s[i]必须是与p[j-1]相匹配的字母。这说明什么呢？刨除s[i]之外，前面的字符串也必须与p[1..j]匹配。所以记录 prob2 = (s[i]==p[j-1]||p[j-1]=='.') && dp[i-1][j]. 注意之前说的“s[i]必须是与p[j-1]相匹配”，不仅仅指二者是相同的字母，后者也可以是'.'。

那么综上，第3点情况下，dp[i][j] = prob1 || prob2

以上搭起了dp方程的框架。

        for (int i=1; i<=M; i++)
            for (int j=1; j<=N; j++)
            {
                if (isalpha(p[j]))
                {
                    dp[i][j] = (s[i]==p[j] && dp[i-1][j-1]);
                }
                else if (p[j]=='.')
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else if (p[j]=='*')
                {
                    bool temp1 = dp[i][j-2];
                    bool temp2 = dp[i-1][j] && (s[i]==p[j-1] || p[j-1]=='.');
                    dp[i][j] = temp1 || temp2;
                }                
            }

接下来我们考虑边界条件。我们注意到上面框架中有几处可能的越界情况：

1. 当j==1时，dp[i][j-2]的第二个下标未定义。但是我们发现当j==1时，p[j]不可能是星号，否则不是合法的表达式。所以这种边界情况我们不用担心。
2. 当j==2时，dp[i][j-2]的第二个下标未定义。所以我们需要考虑dp[i][0]的情况。这种情况下应该都是false，包含在了初始值中。
3. 当i==1时，dp[i-1][j]的第一个下表未定义。所以我们需要考虑dp[0][j]的情况。这对于p来说只可能是非常特殊的一类字符，即类似"a*b*c*"这类的，并且这里的星号都代表重复零次。其他任何p的表达式都不可能被parse成为一个空字符串。所以我们只要对这一类特殊情况做判断就行。

与此题类似的还有044.Wildcard Matching，其边界条件也很类似，需要特别小心．

Leetcode Link