class Solution {

public:

    bool isMatch(string s, string p) {

        int i, j;

        int m = s.size();

        int n = p.size();

        const char *s1 = s.c_str();

        const char *p1 = p.c_str();

        /**

         * b[i + 1][j + 1]: if s[0..i] matches p[0..j]

         * if p[j] != '*'

         * b[i + 1][j + 1] = b[i][j] && s[i] == p[j]

         * if p[j] == '*', denote p[j - 1] with x,

         * then b[i + 1][j + 1] is true iff any of the following is true

         * 1) "x*" repeats 0 time and matches empty: b[i + 1][j -1]

         * 2) "x*" repeats 1 time and matches x: b[i + 1][j]

         * 3) "x*" repeats >= 2 times and matches "x*x": s[i] == x && b[i][j + 1]

         * '.' matches any single character

         */

        bool b[m + ][n + ];

        b[][] = true;

        for (i = ; i < m; i++)

        {

            b[i + ][] = false;

        }

        // p[0..j - 2, j - 1, j] matches empty iff p[j] is '*' and p[0..j - 2] matches empty

        for (j = ; j < n; j++)

        {

            b[][j + ] = j >  && '*' == p1[j] && b[][j - ];

        }

        for (i = ; i < m; i++)

        {

            for (j = ; j < n; j++)

            {

                if (p[j] != '*')

                {

                    b[i + ][j + ] = b[i][j] && ('.' == p1[j] || s1[i] == p1[j]);

                }

                else

                {

                    b[i + ][j + ] = b[i + ][j - ] && j >  || b[i + ][j] ||

                                b[i][j + ] && j >  && ('.' == p1[j - ] || s1[i] == p1[j - ]);

                }

            }

        }

        return b[m][n];

    }

};