通配符匹配

题目描述：

代码实现：

• 回溯法，本题主要的难点在于如何解决’‘的问题，由于’‘可以匹配任意长度的字符串，那么我们就可以通过记录‘’的位置通过回溯的方法来解决这个问题，先让 ‘’匹配 0 个字符，如果匹配 0 个字符不成功，则根据之前记录的 sStarIdx 和 pStarIdx 回溯到这个地方，再让‘*’匹配 1 个字符，如果匹配 1 个字符也不成功，则继续回溯回来，匹配 2 个字符，以此类推。
• 时间复杂度：O(min(S,P))

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    var sIdx = 0, pIdx = 0, sStarIdx = -1, pStarIdx = -1
    while (sIdx < s.length) {
        if (pIdx < p.length && (s[sIdx] === p[pIdx] || p[pIdx] === '?')) {
            sIdx++
            pIdx++
        } else if (pIdx < p.length && p[pIdx] === '*') {
            sStarIdx = sIdx
            pStarIdx = pIdx++
        } else if (pStarIdx > -1) { 
            sIdx = ++sStarIdx
            pIdx = pStarIdx + 1
        } else {
            return false
        }
    }
    while (pIdx < p.length) {
        if (p[pIdx++] !== '*') {
            return false
        }
    }
    return true
};