regular expression - using dynamic programming analysis

regular expression match - using dynamic programming

// Case 1: char matches = isMatch[i-1][j-1] && s[si] == p[pi]
    //      S "aa" "aa" 
    //      P "aa" "ba" 
    // Case 2: dot matches  = isMatch[i-1][j-1] && p[pi] == '.'
    //      S "aa" "aa" 
    //      P "a." "b." 
    // Case 1 & Case 2 can be combined
    // Case 3: *
    //     3a - 0 matches
    //          s: "a"    or "b"      or ""    or "b"
    //          p: "ax*"     "ax*"       "x*"     ".*"
    //              T         F           T        T
    //    isMatch = isMatch[i][j-2]
    //     3b - 1 match
    //          s: "ax"    or "bx"      or "ab"   or "ab"   
    //          p: "ax*"      "ax*"        "a.*"  or "c.*"          
    //               T          F           T          F
    //    isMatch = isMatch[i-1][j-2] && s[si] == p[pi - 1] || p[pi - 1] == '.'
    //     3c - 1+ match
    //          s: "xx"    or "xxx"   or  "bx"    or "bbx"
    //          p: "x*"       "x*"        "x*"       "x*"
    //              T          T           F          F
    //            1 will be handled in 1 match and the rest will succeed because of 0 match 
    //    isMatch = isMatch[i-1][j] && s[si] == p[pi - 1] || p[pi - 1] == '.'