leetcode算法第10题正则表达式匹配回溯动态规划

7次阅读

共计 5021 个字符，预计需要花费 13 分钟才能阅读完成。

题目

简要贴下题目，具体详见这里：

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。

‘*’ 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s)，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。

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

示例 1:

输入:

s = “aa”

p = “a”

输出: false

解释: “a” 无法匹配 “aa” 整个字符串。

解题过程

初始想法

首先我在没有背景知识的情况下，素人想法，从字符串 s 第一个字符开始与正则中第一个 pattern 匹配，如果符合，则看第二个字符是否符合第一个 pattern，如果不符合则看下是否符合第二个 pattern。这样相当于有两个游标在字符串和正则上向后游动，不断匹配，当无法匹配上的时候就是不 match。

回溯

当然这是一个很基础的概念。因为题目中涉及 * 这个可以多次匹配的通配符（其实题目已经很简化了），所以可能出现同一个字符字串匹配到多种 pattern 组合的情况。这就不单单是两个游标依次往下走的问题了。所以我决定先查下正则匹配的通用规则。

像上面提到的这个问题就涉及到回溯问题了，举个简单的例子：

字符串：abbbc

正则：/ab{1,3}bbc/

匹配的过程是：

第 6 步由于 c 没法和 b{1,3} 后面的 b 匹配上，所以我们把与 b{1,3} 匹配上的 bbb 吐出一位（也就是回退一位）拿这个 b 去匹配正则 b{1,3} 后面的b。这种由于往前走尝试一种路径（或者匹配规则）走不通，需要尝试另一种路径的方式叫做回溯。在稍微复杂的正则中可能一次匹配的过程中会涉及非常多次的回溯。稍微详尽的例子看这里。

代码

按照初步掌握的知识先尝试写写看（会结合注释和伪代码）：

// 主函数
function isMatch(s, p) {}

我想了下由于在匹配的过程中需要把整个正则拆分成小的子 pattern，那么我先把 p 分解了，省的游标一边向后走，一边还要判断解析正则。思路是把[a-z], ., [a-z], . 分别摘出来。


// 主函数
function isMatch(s, p) {let patterns = toPatterns( p);
  // 开始匹配
}

function toPatterns(p) {let result = [];
  if (p.length===0) {return result;}

  for(let i = 0; i < p.length;) {let currentP = p[ i];
    let nextP = p[i+1];

    if (nextP!=='*') {
      // 单个字母
      if (
        currentP !== '.' &&
        currentP !== '*'
      ) {
        result.push( {
          type: 'char',
          keyword: currentP
        } );
        i++;
        continue;
      }
      // 单个.
      if (currentP==='.') {
        result.push( {type: '.'} );
        i++
        continue;
      }
      // 单个 * 
      if (currentP==='*') {throw 'invalid pattern';}
    } else {if ( currentP==='.') {
        result.push( {type: '.*'} );
        i += 2;
        continue;
      } else {
        result.push( {
          type: 'char*',
          keyword: currentP
        } );
        i += 2;
        continue;
      }
    }
  }

  return result;
}

然后开始循环判断：

// 主函数
function isMatch(s, p) {let patterns = toPatterns( p);
  // 开始匹配
  /* 
  先判断边际条件
    s 为空 p 为空
    s 为空
    p 为空
  的情况，具体代码就省略了
  */
  let subPattern = patterns.shift();
  let strIndex = 0;

  // 当 patterns 和 s 都轮询完了才算完结
  while(
    subPattern ||
    strIndex < s.length;
  ) {
    // 用字符和正则的子模式进行比较
    if ( 
      subPattern && 
      subPattern.type==='char' 
      s[strIndex]===subPattern.keyword
    ) {// 如果是 [a-z] 的正则，且匹配上了，那么字符串和正则都需要往下走一步：subPattern = patterns.shift();
      strIndex++
    } else if (// 如果是 . 的正则匹配上了) {
      // 字符串和正则都需要往下走一步：subPattern = patterns.shift();
      strIndex++
    } else if (// 如果是 [a-z]* 的正则匹配上了
    ) {
      // 字符串下走一步，正则还可以用
      strIndex++
    } else if (// 如果是 .* 的正则匹配上了) {
      // 字符串下走一步，正则还可以用
      strIndex++
    } else {// 如果没有匹配上，这里就开始考虑！！！回溯！！！}
  }


}

function toPatterns(p) {// 省略}

代码写到这里，我发现了个问题，如果要回溯，我要用非常多的变量记录各种情况，写很多分支条件，没法写啊。参考了别人的代码，发现把循环该成递归，能很好的解决这个问题（针对这道题目只有 [a-z], . 的情况会产生回溯）：

var isMatch = function(s, p) {return isMatchImpl( s, toPatterns(p) );
};

function toPatterns(p) {// 省略}

function isMatchImpl(s, patterns) {
  // 开始匹配
  /* 
  先判断边际条件
    s 为空 patterns 为空
    s 为空
    patterns 为空
  的情况，具体代码就省略了
  */
  let p = patterns[0];
  if (
    p.type==='char' &&
    s[0]===p.keyword
  ) {return isMatchImpl( s.substr(1), patterns.slice(1) );
  } else if (
    p.type==='.' &&
    s[0]
  ) {return isMatchImpl( s.substr(1), patterns.slice(1) );
  } else if (p.type==='char*') {if ( s[ 0]===p.keyword ) {
      // 这里通过逻辑或和递归，把回溯的各个条件依次执行
      return isMatchImpl(s, patterns.slice(1) ) || isMatchImpl(s.substr(1), patterns ) || isMatchImpl(s.substr(1), patterns.slice(1) );
    } else {
      // 这里通过逻辑或和递归，把回溯的各个条件依次执行
      return isMatchImpl(s, patterns.slice(1) )
    }
  } else if (p.type==='.*') {if ( s) {
      // 这里通过逻辑或和递归，把回溯的各个条件依次执行
      return isMatchImpl(s, patterns.slice(1) ) || isMatchImpl(s.substr(1), patterns ) || isMatchImpl(s.substr(1), patterns.slice(1));
    } else {
      // 这里通过逻辑或和递归，把回溯的各个条件依次执行
      return isMatchImpl(s, patterns.slice(1) );
    }
  } else {return false;}
}

看下代码里面的注释，通过逻辑或的逻辑短路原则，结合递归，就把回溯的各个路径写成一行了。循环和递归真是好基友，各有各的适用场景。代码的功能完成了，通过了官方的测试用例。

动态规划

代码完成了，但是执行效率很有问题。看下上面讲回溯例子时候的图片，当回溯的时候如果 subpattern 没有变，且 strindex 没有变，那么结果是一致的，也就是说如果多次执行可以被记录下来，不用每次都判断 subPattern 和 s[strIndex] 是否匹配。这个思路和优化斐波那契数列是否有点相似，就是对计算过的结果用空间换时间，对于相同的计算条件只需要计算一次。这个思路再加上这道题目，背后的原理其实就是动态规划的概念。

我简单说下什么叫动态规划：

  1. 将待求解的问题分解为若干个子问题。
  2. 按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
  3. 在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。

这个好像和我们正则匹配的过程不谋而合了：

  1. 匹配的过程是必须每个 subpattern 都匹配成功。
  2. 下一个 subpattern 所要匹配的字符取决于上一个 subpattern 用到哪个字符。
  3. 当一条匹配路径走不通，通过回溯寻找另一条可能的匹配路径。

而动态规划在算法中的应用，其一大优化策略就是充分利用前面保存的子问题的解来减少重复计算。所以改造下代码：

const P_TYPE_CHAR = 1;
const P_TYPE_ANY_CHAR = 2;
const P_TYPE_CHAR_ANY_TIME = 3;
const P_TYPE_ANY_CHAR_ANY_TIME = 4;
const Q_DOT = '.';
const Q_STAR = '*';
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {return isMatchImpl( s, 0, toPatterns(p), 0 );
};



function toPatterns(p) {// 省略}

let Cache = {};

function isMatchImpl(s, sIndex, patterns, pIndex) {if ( sIndex===s.length && pIndex===patterns.length) {return true;}
  if (sIndex < s.length && pIndex===patterns.length) {return false;}

  let cacheKey = `${sIndex}-${pIndex}`;
  if (Cache[cacheKey]!==undefined ) {return Cache[cacheKey];
  }

  let p = patterns[pIndex];
  
  if (
    p.type===P_TYPE_CHAR &&
    s[sIndex]===p.keyword
  ) {Cache[ cacheKey] = true;
    return isMatchImpl(s, ++sIndex, patterns, ++pIndex);
  } else if (
    p.type===P_TYPE_ANY_CHAR &&
    s[sIndex]
  ) {Cache[ cacheKey] = true;
    return isMatchImpl(s, ++sIndex, patterns, ++pIndex);
  } else if (p.type===P_TYPE_CHAR_ANY_TIME) {Cache[ cacheKey] = true;
    if (s[ sIndex]===p.keyword ) {return isMatchImpl( s, sIndex, patterns, ++pIndex) || isMatchImpl(s, ++sIndex, patterns, pIndex) || isMatchImpl(s, ++sIndex, patterns, ++pIndex);
    } else {Cache[ cacheKey] = false;
      return isMatchImpl(s, sIndex, patterns, ++pIndex)
    }
  } else if (p.type===P_TYPE_ANY_CHAR_ANY_TIME) {Cache[ cacheKey] = true;
    if (s) {return isMatchImpl( s, sIndex, patterns, ++pIndex) || isMatchImpl(s, ++sIndex, patterns, pIndex) || isMatchImpl(s, ++sIndex, patterns, ++pIndex);
    } else {return isMatchImpl( s, sIndex, patterns, ++pIndex);
    }
  } else {Cache[ cacheKey] = false;
    return false;
  }

}

参考文献

  1. https://zhuanlan.zhihu.com/p/…
  2. http://www.cnblogs.com/steven…
正文完
算法
发表至：无分类
2019-05-24
 0
-「」

Just My Socks（注册教程 内含优惠码）

Just My Socks