JavaScriptで正規表現マッチングを実装する方法 ― 「.」と「*」を動的計画法で処理する

入力文字列 str とパターン p が与えられたとき、「.」と「*」をサポートする正規表現マッチングを実装することを考えます。

各記号の役割は以下のとおりです。

• . → 任意の1文字にマッチします。

• * → 直前の要素の0回以上の繰り返しにマッチします。

なお、マッチングは入力文字列の全体に対して成立しなければなりません（部分一致ではありません）。

前提条件

• str は空文字列の可能性があり、含まれるのは小文字の a〜z のみです。

• p は空文字列の可能性があり、含まれるのは小文字の a〜z、および「.」や「*」などの記号のみです。

例

たとえば、入力が次の場合を考えます。

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

この場合、出力は false になります。パターン「a」は文字列「aa」全体にはマッチしないためです。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を用いて効率的に解くことができます。2次元のブール値テーブル match を用意し、match[i][j] を「文字列の先頭 i 文字と、パターンの先頭 j 文字がマッチするかどうか」を表すようにします。

遷移のルール

• パターンの現在の文字が「*」の場合：直前の要素を0回繰り返す（パターンを2文字分スキップ）ケースと、直前の要素が現在の文字と一致するか「.」である場合に1回以上の繰り返しとしてマッチを伸ばすケースのいずれかを検討します。

• パターンの現在の文字が通常の文字または「.」の場合：文字列の現在の文字と一致する（または「.」である）なら、直前のマッチ結果をそのまま引き継ぎます。

コード

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

出力結果

コンソールには次のように出力されます。

true

パターン「c*a*b」は「cを0回以上、その後にaを0回以上繰り返す」という意味になるため、文字列「aab」全体にマッチし、結果は true となります。