JavaScript中的正则表达式匹配

Z时代
2024-01-10
分类：综合

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

这些符号的功能应为-

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

匹配项应覆盖整个输入字符串（而不是部分）。

注意

str可以为空，并且仅包含小写字母az。
p可以为空，并且仅包含小写字母az和类似字符。要么 *。

例如-

如果输入是-

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'));