JavaScript 中的正则表达式匹配

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 9:16:17

假设我们给定一个输入字符串 str 和一个模式 p，我们需要实现支持 . 和 * 的正则表达式匹配。

这些符号的功能应该是 −

. --> 匹配任何单个字符。
* --> 匹配零个或多个前面的元素。

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

注意

str 可以为空，并且只包含小写字母 a-z。
p 可以为空，并且只包含小写字母 a-z 以及类似的字符。或 *。

例如 −

如果输入是 −

const str = 'aa';
const p = 'a';

那么输出应该是 false，因为 a 与整个字符串 aa 不匹配。

示例

以下是代码 −

const regexMatching = (str, p) => {
   const ZERO_OR_MORE_CHARS = '*';
   const ANY_CHAR = '.';
   const match = Array(str.length + 1).fill(null).map(() => {
      return Array(p.length + 1).fill(null);
   });
   match[0][0] = true;
   for (let col = 1; col <= p.length; col += 1) {
      const patternIndex = col - 1;
      if (p[patternIndex] === ZERO_OR_MORE_CHARS) {
         match[0][col] = match[0][col - 2];
      } else {
         match[0][col] = false;
      }
   }
   for (let row = 1; row <= str.length; row += 1) {
      match[row][0] = false;
   }
   for (let row = 1; row <= str.length; row += 1) {
      for (let col = 1; col <= p.length; col += 1) {
         const stringIndex = row - 1;
         const patternIndex = col - 1;
         if (p[patternIndex] === ZERO_OR_MORE_CHARS) {
            if (match[row][col - 2] === true) {
               match[row][col] = true;
            } else if (
               (
                  p[patternIndex - 1] === str[stringIndex]
                  || p[patternIndex - 1] === ANY_CHAR
               )
               && match[row - 1][col] === true
            ) {
                  match[row][col] = true;
            } else {
               match[row][col] = false;
            }
         } else if (
            p[patternIndex] === str[stringIndex]
            || p[patternIndex] === ANY_CHAR
         ) {
               match[row][col] = match[row - 1][col - 1];
            } else {
               match[row][col] = false;
            }
         }
      }
      return match[str.length][p.length];
};
console.log(regexMatching('aab', 'c*a*b'));