0ms runtime. 3 golang solutions with optimization and explaination. Recursive | Iterative | DP.
This is a wonderful problem, and deserves serious study.\n\n1. Recursive solution.  It\'s not complicated. \n\n\nfunc isMatch(s string, p string) bool {\n    if
This is a wonderful problem, and deserves serious study.\n\n1. Recursive solution.  It\'s not complicated. \n\n```\nfunc isMatch(s string, p string) bool {\n    if len(p) == 0 {\n        return len(s) == 0\n    }\n    if len(s) > 0 && (s[0] == p[0] || p[0] == \'?\') {\n        return isMatch(s[1:], p[1:])\n    } else if p[0] == \'*\' {\n        return isMatch(s, p[1:]) || (len(s) > 0 && isMatch(s[1:], p))\n    }\n    return false\n}\n```\nUnfortunately it is judged Time Limit Exceeded.  The test cases is specially designed  for recursive algorithms.\n\n<img src="https://assets.leetcode.com/users/images/de901b4d-393d-42e1-9a8c-c0c11a7218b6_1607409296.4703355.png" width="450px" />\n\nLet\'s do some optimization works.\n \nOptimization 1: Pruning unnecessary recursive calls.\nThinking about this testcase `assert.False(t, isMatch("bbc", "*b*a"))`. Every time we match `*`, if the string can\'t match the subsequent pattern, the recursive function will call itself two times, the call tree forks.\n\n```\nisMatch("bbc", "*b*a")         \n  |\n  |-isMatch("bbc", "b*a")   \n  |   |\n  |   |-isMatch("bc", "*a")    \n  |       |\n  |       |-isMatch("bc", "a")\n  |       |\n  |       |-isMatch("c", "*a")  // First fork\n  |           |                 \n  |           |-isMatch("c", "a")\n  |           |\n  |           |-isMatch("", "*a") // Second fork return false. This means that any suffix substring can\'t match the sub pattern \n  |                               // starts with the last `*`. "c","bc","bbc", none of them can match "*a". \n  |                               // **AND OF COURCE** they can\'t match any pattern ends with "*a", such as "b*a","*b*a". This\'s the untimate match.\n  |\n  |-isMatch("bc", "*b*a")  // Third fork, This fork branch is unnecessary, because the result is \n\t  |                    // already known after calling isMatch("", "*a").\n      |\n      |-isMatch("bc", "b*a")\n      |   |\n      |   |-isMatch("c", "*a")\n      |....  \n```\nNow we know that after matching the pattern starts with the last `*`, any recursive call fork is unnecessary.\nTo avoid alll the unnecessary recursive forks we only need to add a `lastStar` variant and set the `lastStar` to `true` after matching the pattern starts with the last `*`. \nSo, here is the optimized solution:\n\n\n\n```\nfunc isMatch(s string, p string) bool { \n    var lastStar bool\n    var helper func(s, p string) bool\n    helper = func(s, p string) bool {\n        if len(p) == 0 {\n            return len(s) == 0\n        }\n        var matched bool\n        if len(s) > 0 && (p[0] == \'?\' || s[0] == p[0]) {\n            matched = helper(s[1:], p[1:])\n        } else if p[0] == \'*\' {\n            matched = len(p) == 1 || helper(s, p[1:]) // cut the pattern string first\n            if !lastStar && !matched && len(s) > 0 {\n                matched = helper(s[1:], p) // When running to this line for the first time, the pattern string must start with the last `*`, then cut the string.\n                lastStar = true\n            }\n        }\n        return matched\n    }\n    return helper(s, p)\n}\n```\n\nOptimization 2: Two directions match.\nAbout this testcase `s="abababababababa", p="*b*b*b*b*e"`, the solution do many useless work with the prefix containing many `*`, but the last char "a" doesn\'t match "e", and it\'s easy to get. If matching in two directions, back to front and front to back, it can save some time.\n\n```go\nfunc isMatch(s string, p string) bool {\n    var lastStar, frontToBack bool\n    var helper func(s, p string) bool\n    helper = func(s, p string) bool {\n        if len(p) == 0 {\n            return len(s) == 0\n        }\n        var matched bool\n        if frontToBack {\n\t\t\tif len(s) > 0 && (p[0] == \'?\' || s[0] == p[0]) {\n\t\t\t\tmatched = helper(s[1:], p[1:])\n\t\t\t} else if p[0] == \'*\' {\n\t\t\t\tmatched = len(p) == 1 || helper(s, p[1:])\n\t\t\t\tif !lastStar && !matched && len(s) > 0 {\n\t\t\t\t\tmatched = helper(s[1:], p)\n\t\t\t\t\tlastStar = true\n\t\t\t\t}\n\t\t\t}\n        } else {\n            if len(s) > 0 && (p[len(p)-1] == \'?\' || s[len(s)-1] == p[len(p)-1]) {\n                matched = helper(s[:len(s)-1], p[:len(p)-1])\n            } else if p[len(p)-1] == \'*\' {\n    \t\t\tfrontToBack = true\n                matched = len(p) == 1 || helper(s, p) //Matching from front to back\n            }\n\t\t}\n        return matched\n    }\n    return helper(s, p)\n}\n```\n\n2. Iterative solution.\nThis solution is based on the same idea of the optimized recursive solution. When matching `*`, first we compare the follow up chars, if it doesn\'t match, we just backtrack to the last star. \n\n```go\nfunc isMatch(s string, p string) bool {\n\tvar i, j, matched, lastStar int\n    lastStar = -1\n\tfor i < len(s) {\n\t\tif j < len(p) {\n\t\t\tif p[j] == \'?\' || s[i] == p[j] {\n\t\t\t\ti, j = i+ 1, j+ 1\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\tif p[j] == \'*\' {\n\t\t\t    matched, lastStar = i, j\n                j++\n\t\t\t\tcontinue\n\t\t\t}\n\t\t}\n\t\tif lastStar < 0 {\n\t\t    return false\n        }\n        matched++ // let s[i] matches \'*\'\n        i, j = matched, lastStar+1\n\t}\n\t\n\tfor ; j < len(p); j++ {\n\t\tif p[j] != \'*\' {\n\t\t\treturn false\n\t\t}\n\t}\n\treturn true\n}\n```\n\nOptimization: Two directions match.\n\n```go\nfunc isMatch(s string, p string) bool {\n    var i, j, matched, lastStar, lastI, lastJ int\n\t//match from end to front until the last star\n    for lastI, lastJ = len(s)-1, len(p)-1; lastI >= 0 && lastJ >= 0 &&  p[lastJ] != \'*\'; {\n\t    if p[lastJ] == \'?\' || s[lastI] == p[lastJ] {\n            lastI, lastJ = lastI-1, lastJ-1\n        } else {\n            return false\n        }\n    }\n    if lastJ < 0 {\n        return lastI < 0\n    }\n    if lastI < 0 {\n        for j=0; j<=lastJ; j++ {\n            if p[j] != \'*\' {\n                return false\n            }\n        }\n        return true\n    }\n\tlastStar = -1\n\t//match from front to end\n    for i <= lastI {\n        if j <= lastJ {\n            if p[j] == \'?\' || s[i] == p[j] {\n                i, j = i+1, j+1\n                continue\n            }\n            if p[j] == \'*\' {\n                matched, lastStar = i, j\n                j++\n                continue\n            }\n        }\n        if lastStar < 0 {\n            return false\n        }\n        matched++\n        i, j = matched, lastStar+1\n    }\n\n    for ; j <= lastJ; j++ {\n        if p[j] != \'*\' {\n            return false\n        }\n    }\n    return true\n}\n```\n\nActually I think this solution is ugly. Bu it can get `0ms` running time.\n<img src="https://assets.leetcode.com/users/images/dfb37fff-ed39-456b-95b1-be03e16e69fe_1607334056.0733168.png" width="500px" />\n\n3. DP solution.\n\n```\nfunc isMatch(s string, p string) bool {\n    if len(p) == 0 {\n        return len(s) == 0\n    }\n    dp := make([][]bool, len(p) + 1)\n    for i := 0; i < len(dp); i++ {\n        dp[i] = make([]bool, len(s) + 1)\n    }\n    dp[0][0] = true\n    for i:=1;i<=len(p);i++ {\n        dp[i][0] = dp[i-1][0] && p[i-1] == \'*\'\n        for j := 1; j <= len(s); j++ {\n            switch p[i-1] {\n            case \'?\':\n                dp[i][j] = dp[i-1][j-1]\n            case \'*\':\n                dp[i][j] = dp[i-1][j] || dp[i][j-1]\n            default:\n                dp[i][j] = dp[i-1][j-1] && p[i-1] == s[j-1]\n            }\n        }\n    }\n    return dp[len(p)][len(s)]\n}\n```\n\nOptimization:\n\n1.About this testcase `s="abcdefghi", p="*fghi"`, after loop in which match `f`, the dp row is `[0,0,0,0,0,0,1,0,0,0]`, in the next loop which is to match `g`, we don\'t need start from the beginning char `a`. We just start from `f` which is true correspondingly in dp array . So by saving the first matched position of last loop  to variant `firstMatch`, we can start from `firstMatch` directly in the next loop.  Also We don\'t need match `gh` to pattern `f`, because all behind cells are False. So we can save the last matched position to `lastMatch`, if next pattern char isn\'t `*`, in next loop, we can stop at `lastMatch + 1`.\n2.About this testcase `s="ddddddddfdfdfd", p="d*******d"`,  the continuous `*` is exactly same as the pattern "*" with only one star. We can shrink the redundant `*`s to single `*` at the beginning. \n3. By shrinking the pattern string, we can count the number of `non-*` chars. That can help to reduce loop length of matching `*`. In testcase `s="abcdefg", p="*?*?*?`, there are 3 `non-*` chars, so in the first loop of matching `*`, we can just stop matching at char `d`, because there are 3 more `non-*` chars in the subsequent pattern.\n4. About this testcase `s="ddddddddfdfdfd", p="aaaaaaaaaaa"`, we don\'t need to run to the end to get the result from `dp[len(s)][len(p)]`.  After the first pattern `\'a\'` we already know the string doesn\'t match the pattern. The subsequent runs are meaningless.\n5. Space optimization using an arrays instead of 2-d arrays. Reduce space from len(s)\\*len(p)  to len(s). \n```go\n\t...\n\tswitch p[i-1] {\n\tcase \'?\':\n\t\tdp[i][j] = dp[i-1][j-1]\n\tcase \'*\':\n\t\tdp[i][j] = dp[i-1][j] || dp[i][j-1]\n\t...\n```\nIn dp solution, determining a cell in the 2-d array need three cells which respectively are the left cell, the top cell and the left top cell.\n|a|b|c|.|\n|-|-|-|-|\n|**d**|*e*|f|.|\n|.|.|.|.|\nIn the example in the table above, Determining cell `e` depends on `a`,`b` and `d`.  \nTo optimize the space, We can use a temporary variant `dpCur` save the  temporary result of cell `e`, because cell `e` is needed in determing cell \'f\'. We can  put `dpcur` into cell `e` after determing cell `f`.\n\n```go\nfunc isMatch(s string, p string) bool {\n    if len(p) == 0 {\n        return len(s) == 0\n    }\n    //shrink redundant `*`.\n    var charCount int\n    var b bytes.Buffer\n    for i := 0; i < len(p); i++ {\n        if p[i] != \'*\' || i == 0 || p[i] != p[i-1] {\n            b.WriteByte(p[i])\n            if p[i] != \'*\' {\n                charCount++\n            }\n        }\n    }\n    if charCount > len(s) {\n        return false\n    }\n    if b.Len() < len(p) {\n        p = b.String()\n    }\n\t\n    var dp = make([]bool, len(s)+1)\n    dp[0] = true\n    var firstMatch,stopMatch, lastMatch,dpCur = 1,0,0,true\n\t\n    for i := 1; i <= len(p); i++ {\n        dpCur = dp[firstMatch-1] && p[i-1] == \'*\'\n        matched := dpCur\n        if p[i-1] == \'*\' {\n            stopMatch = len(s) - charCount\n        } else {\n            charCount--\n\t\t\tstopMatch = lastMatch + 1\n\t\t\t// Don\'t worry about overflow if `stopMatch > len(s)`. It won\'t happen.\n        }\n        for j := firstMatch; j <= stopMatch; j++ {\n            switch p[i-1] {\n            case \'?\':\n                dpCur, dp[j-1] = dp[j-1], dpCur\n            case \'*\':\n                dpCur, dp[j-1] = dpCur || dp[j], dpCur\n            default:\n                dpCur, dp[j-1] = dp[j-1] && p[i-1] == s[j-1], dpCur\n            }\n            if dpCur {\n                if !matched {\n                    firstMatch = j\n                    matched = true\n                }\n                lastMatch = j\n            }\n        }\n        if !matched {\n            //we already know s[:j] doesn\'t match p[:i]. So we don\'t need more comparing.\n            return false\n        }\n        dp[stopMatch] = dpCur\n    }\n    return dp[len(s)]\n}\n```\n\nI will be really surprised if someone can keep reading to here.
['Dynamic Programming', 'Recursion', 'Go']