一天一大 leet(通配符匹配)难度:困难-Day20200705

题目:

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例

• 示例1

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

• 示例2

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

• 示例3

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

• 示例4

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

• 示例5

输入:
s = "acdcb"
p = "a*c?b"
输出: false

抛砖引玉

---

这题和之前的一道正则表达式匹配很相似 留下链接：day-20：正则表达式匹配 (难度:困难)

看下两题的不同点：

1. 正则表达式匹配:

• '*'的规则是：知道其前面的字符出现n次（n>=0）
• '.'可以做任何单个字符(很像斗地主的癞子，哈哈)

2. 本题:

• '*'的规则是：可以做任意字符串包括空
• '?'可以做任何单个字符(和上面'.'癞子一样)

感觉之后可以把相似的题目归到一起，先做个TODO待之后有时间弄吧

---

逐位匹配

• 设s长len1,p长ken2
• 声明一个len1+1（索引i）,每个子集长len2+1（索引j）的数组dp存贮:s到第i与p到第j位是否匹配(默认不匹配false)
• 数组长度和子集长度的增加1为保存为空的情况

变量声明：

• s指针i，第i个元素为$s_i-1$,存放位置s[i]
• p指针j，第i个元素为$p_j-1$,存放位置p[j]

特殊情况：

• i = 0,j = 0 ,匹配（true）dp[0][0] = true
• 当s指针在空位置时，p中能与其匹配的只有'*'后面一位:dp[0][j]

指针切换时的逻辑判断：

• $s_i-1$等于$p_j-1$，那匹配的结果和上一次一样dp[i-1][j-1]，即上一次匹配成功就沿用成功失败就沿用失败
• $p_j-1$等于'?'，'?'可以转换成$s_i-1$，则那匹配的结果也和上一次一样dp[i-1][j-1]
• $p_j-1$等于'*'：
  • '*'转换成空：p忽略这一位，那匹配结果就为$s_i-1$与$p_j$比较的结果
  • '*'转换成字符串：s的指针逐个向后移去尝试与p匹配（在i迭代中完成该逻辑），并记录与其匹配的结果到dp[i][j-1]中
  • 以上区或这样一种匹配，指针所截取的字符就匹配

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    if (s == null || p == null) return false
    let len1 = s.length,
    len2 = p.length
    let dp = new Array(len1 + 1)
    for (let i = 0; i < dp.length; i++) dp[i] = new Array(len2 + 1).fill(false);
    dp[0][0] = true
    for (let j = 1; j < len2+1; ++j) {
        if (p[j - 1] == '*') {
            dp[0][j] = true;
        }
        else {
            break;
        }
    }
    for (let i = 1; i < len1 + 1; ++i) {
        for (let j = 1; j <= len2; ++j) {
            if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
            else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[len1][len2];
};

官方答案

贪心算法

• 字符匹配的规则中单个字符相等或者'?'替换的字符相等都是单个单个字符的匹配，只是'*'的出现会打断这种单个单个匹配的规则
• 那使用''对模式字符串p进行分割，之后对每个分割后的字符单独匹配($u_x$)： ?u_1U_2...u_x?

实现

先对s和p倒序匹配：

• p 的最后一个字符是星号，那么 s 未匹配完，那么没有关系
• 如果 p 没有匹配完，那么 p 剩余的字符必须都是星号

再对s和p正序(分割)匹配：

• 匹配所有能匹配的u_x，如果还剩余包含'*'的无效u_x则说明匹配失败

变量声明：

• sIndex，当前遍历到s的位置
• pIndex，当前遍历到p的位置
• sRecord，s的起始位置
• pRecord，p的起始位置

起始位置的设定:

• 倒序起始位置为字符串length-1
• 正序时，如果设sRecord和pRecord都为0，那么如果p起始位不是*那么$u_1$则无法准确获得， 则默认sRecord=0，pRecord=-1，标记$u_x$开始

模式p分割$u_x$形式说明：

• 模式 p 的开头字符不是'*' -> s和p正序(分割)匹配
• 模式 p 的结尾字符不是'*' -> s和p倒序匹配

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let sRight = s.length, 
        pRight = p.length;

    // s和p倒序匹配
    // p 的最后一个字符是星号，那么 s 未匹配完，那么没有关系
    // 如果 p 没有匹配完，那么 p 剩余的字符必须都是星号
    while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
        if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
            --sRight;
            --pRight;
        } else {
            return false;
        }
    }
    if (pRight == 0) {
        return sRight == 0;
    }

    let sIndex = 0, 
        pIndex = 0;
    let sRecord = -1, 
        pRecord = -1;

    // s和p正序(分割)匹配
    while (sIndex < sRight && pIndex < pRight) {
        // 遇到'*'，说明找到了 u_x，开始寻找 u_x+1
        if (p.charAt(pIndex) == '*') {
            ++pIndex;
            // 更新p和s的起始位置
            sRecord = sIndex;
            pRecord = pIndex;
        } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
            // 如果匹配，就继续寻找 u_x 的下一个字符
            ++sIndex;
            ++pIndex;
        } else if (sRecord != -1 && sRecord + 1 < sRight) {
            // 如果不匹配，那么需要重新寻找 u_x
            ++sRecord;
            sIndex = sRecord;
            pIndex = pRecord;
        } else {
            // 如果不匹配并且下一个起始位置不存在，那么匹配失败
            return false;
        }
    }

    // 匹配所有能匹配的u_x，如果还剩余包含'*'的无效u_x则说明匹配失败
    return allStars(p, pIndex, pRight);

    // 分割u_x，指定位置区间中包含'*'则说明是无效的u_x
    function allStars(str,left,right) {
        for (let i = left; i < right; ++i) {
            if (str.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }
    // 单个字符匹配
    function charMatch(u,v) {
        return u == v || v == '?';
    }
};

其他解法

递增'*'匹配的字符

• 单个单个的好匹配，只是'*'可能代表多个所以才难匹配
• 如果在匹配时枚举出'*'可能匹配的长度，那问题又回归了单个匹配
• 如果能枚举''代替多个字符切剩余的字符能匹配上，则说明匹配上了，即： p由单个与s匹配的字符和''组成

得到'*'匹配的长度：

• 开始位置,p中'*'出现的位置
• 从0开始枚举可能匹配的长度，查找可以匹配完的情况
• 如果匹配完s切p没有剩余则说明匹配成功

未匹配完成的标记为，在下个'*'之前的字母已匹配不上

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    let sIndex = 0,
        pIndex = 0,
        sLen = s.length,
        pLen = p.length,
        sRecord = -1,  // 上一次出现'*'对应的s的位置(sIndex)，默认为-1
        pRecord = -1,     // 上一次出现'*'对应的p的位置(pIndex)
        matches = 0;  // '*'匹配的字符个数，默认为0

  // 遍历目标字符串
  while (sIndex < sLen) {
    // 如果遇到正常字符或者‘？’，两个指针直接递增
    if (pIndex < pLen && (s[sIndex] === p[pIndex] || p[pIndex] === '?')) {
      pIndex++
      sIndex++
    } else if (pIndex < pLen && p[pIndex] === '*') {
        matches = 0
      // 遇到了'*'，记录此时对应的目标字符串的指针
      sRecord = sIndex
      // 记录此时p的指针
      pRecord = pIndex
      // p指针后移一位
      pIndex++
    } else if (sRecord !== -1) {
     // 如果在下一个'*' 出现前p的'?'和字符还没匹配完（pRecord到p[pIndex] === '*'）
     // 则 '*'代表的字母增加一个，回溯开始位置重新匹配
      matches++
      sIndex = sRecord + matches
      pIndex = pRecord + 1
    } else {
      return false
    }
  }

  // 判断此时是否还有‘*’没有遍历完
  while (pIndex < pLen && p[pIndex] === '*') {
    pIndex++
  }

  return pIndex === pLen
}

---

优化：减少中间计数变量（matches）

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let sIndex = 0, 
    pIndex = 0, 
    sRecord = -1, 
    pRecord = -1;
    while (sIndex < s.length) {
        // 如果遇到正常字符或者‘？’，两个指针直接递增
        if (pIndex < p.length && (s[sIndex] === p[pIndex] || p[pIndex] === '?')) {
            sIndex++, 
            pIndex++;
        } else if (pIndex < p.length && p[pIndex] === '*') {
            // 遇到了'*'，记录此时对应的目标字符串的指针
            // 记录如果之后序列匹配不成功时， sIndex和pIndex需要回溯到的位置
            sRecord = sIndex;
            pRecord = pIndex++; 
        } else if (pRecord > -1) { 
            // 发现当前字符不匹配且没有星号 但是 pRecord > -1 
            // 说明可能是 * 之前匹配的字符数量少了 这时回溯，让*匹配的字符增加一个
            sIndex = ++sRecord;
            pIndex = pRecord + 1;
        } else {
            return false;
        }
    }
     //如果 p 中还有多余的字符的话，那必须都是 * 否则 匹配就不成功
    while (pIndex < p.length) if (p[pIndex++] !== '*') return false;
    return true;
};

s中'*'的匹配位置

思路与上面记录匹配数量基本一致

• 声明一个数组cache记录：

1. 0,'*'开始匹配的位置
2. 1,'*'结束匹配的位置

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let cache = [-1,-1],
        slen = s.length,
        plen = p.length,
        pIndex = 0,
        sIndex = 0;
    while(sIndex<slen){
        if(pIndex < plen && (p[pIndex] ==s[sIndex]||p[pIndex] =='*'||p[pIndex] == '?')){
            // 存储'*'要匹配的开始位置
            if(p[pIndex] == '*'){
                cache[0] = pIndex
                cache[1] = sIndex
            } else {
                sIndex += 1
            }
            pIndex += 1
        } else if (cache[0] != -1) {
            // '*'分割的字符串未完成匹配，'*'替换的字符数增加一个试试
            pIndex = cache[0] + 1
            sIndex = cache[1] + 1
            cache[1] += 1
        } else {
            // 如果某个'*'分割的区间没有匹配完说明整个字符串都是不可能匹配的
            return false
        }
    }
    while(pIndex<plen && p[pIndex]=="*") {
        pIndex +=1
    }
    return (pIndex == plen)
};

总结

• 本题匹配的难点在'*'的匹配，因为其数量不固定
• 整体思路就是通过'*'来划分字符判断，然后逐个匹配字符片段，
• '*'来配合字符匹配的判断,从0开始直到查到能匹配的组合

博客: 前端小书童

每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号：前端小书童