การจับคู่ Regular Expression (Regex Matching) ใน JavaScript

ต้อง implement การจับคู่ regular expression รองรับ '.' (match ตัวอักษรเดี่ยวใดๆ) และ '*' (match ศูนย์หรือมากกว่าของตัวอักษรก่อนหน้า) ต้องจับคู่ทั้งสตริง (ไม่ใช่ partial)

ใช้ Dynamic Programming (DP) สร้างตาราง match[m+1][n+1]

ตัวอย่างโค้ด

const regexMatching = (str, p) => {
  const ZERO_OR_MORE_CHARS = '*';
  const ANY_CHAR = '.';
  const match = Array(str.length + 1).fill(null).map(() => Array(p.length + 1).fill(null));
  match[0][0] = true;
  for (let col = 1; col <= p.length; col++) {
    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++) { match[row][0] = false; }
  for (let row = 1; row <= str.length; row++) {
    for (let col = 1; col <= p.length; col++) {
      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