10. Regex matching

10_solution1_tab.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static const char *S, *Pt;

static bool matches(int i, int j) { // s[i-1] vs p[j-1]
  return Pt[j - 1] == '.' || S[i - 1] == Pt[j - 1];
}

bool isMatch(char *s, char *p) {
  int n = strlen(s), m = strlen(p);
  S = s, Pt = p;
  int w = m + 1;
  bool *dp = calloc((n + 1) * w, sizeof(bool)); // dp[i * w + j]
  dp[0] = true;

  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (p[j - 1] == '*') {
        dp[i * w + j] = dp[i * w + (j - 2)]; // zero copies
        if (i > 0 && matches(i, j - 1))
          dp[i * w + j] = dp[i * w + j] || dp[(i - 1) * w + j]; // one more copy
      } else {
        dp[i * w + j] = i > 0 && matches(i, j) && dp[(i - 1) * w + (j - 1)];
      }
    }
  }
  bool res = dp[n * w + m];
  free(dp);
  return res;
}

10_solution2_memo.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static const char *S, *Pt;
static int w;
static int *dp; // dp[i * w + j], -1 = not computed

static bool matches(int i, int j) { // s[i-1] vs p[j-1]
  return Pt[j - 1] == '.' || S[i - 1] == Pt[j - 1];
}

static bool f(int i, int j) {
  if (j == 0)
    return i == 0; // empty pattern matches only empty s
  if (dp[i * w + j] != -1)
    return dp[i * w + j];

  bool res;
  if (Pt[j - 1] == '*') {
    res = f(i, j - 2); // zero copies
    if (!res && i > 0 && matches(i, j - 1))
      res = f(i - 1, j); // one more copy
  } else {
    res = i > 0 && matches(i, j) && f(i - 1, j - 1);
  }
  dp[i * w + j] = res;
  return res;
}

bool isMatch(char *s, char *p) {
  int n = strlen(s), m = strlen(p);
  S = s, Pt = p, w = m + 1;
  dp = malloc((n + 1) * w * sizeof(int));
  for (int k = 0; k < (n + 1) * w; k++)
    dp[k] = -1;
  bool res = f(n, m);
  free(dp);
  return res;
}

10_solution1_tab.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;

    auto matches = [&](int i, int j) {
      return p[j - 1] == '.' || s[i - 1] == p[j - 1];
    };

    for (int i = 0; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (p[j - 1] == '*') {
          dp[i][j] = dp[i][j - 2]; // zero copies
          if (i > 0 && matches(i, j - 1))
            dp[i][j] = dp[i][j] || dp[i - 1][j]; // one more copy
        } else {
          dp[i][j] = i > 0 && matches(i, j) && dp[i - 1][j - 1];
        }
      }
    }
    return dp[n][m];
  }
};

10_solution2_memo.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  bool matches(string &s, string &p, int i, int j) { // s[i-1] vs p[j-1]
    return p[j - 1] == '.' || s[i - 1] == p[j - 1];
  }

  bool f(int i, int j, string &s, string &p, vector<vector<int>> &dp) {
    if (j == 0)
      return i == 0; // empty pattern matches only empty s
    if (dp[i][j] != -1)
      return dp[i][j];

    bool res;
    if (p[j - 1] == '*') {
      res = f(i, j - 2, s, p, dp); // zero copies
      if (!res && i > 0 && matches(s, p, i, j - 1))
        res = f(i - 1, j, s, p, dp); // one more copy
    } else {
      res = i > 0 && matches(s, p, i, j) && f(i - 1, j - 1, s, p, dp);
    }
    return dp[i][j] = res;
  }

  bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return f(n, m, s, p, dp);
  }
};

10_solution1_tab.go

package dp

func isMatch(s string, p string) bool {
    n, m := len(s), len(p)
    dp := make([][]bool, n+1)
    for i := range dp {
        dp[i] = make([]bool, m+1)
    }
    dp[0][0] = true

    matches := func(i, j int) bool { // s[i-1] vs p[j-1]
        return p[j-1] == '.' || s[i-1] == p[j-1]
    }

    for i := 0; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if p[j-1] == '*' {
                dp[i][j] = dp[i][j-2] // zero copies
                if i > 0 && matches(i, j-1) {
                    dp[i][j] = dp[i][j] || dp[i-1][j] // one more copy
                }
            } else {
                dp[i][j] = i > 0 && matches(i, j) && dp[i-1][j-1]
            }
        }
    }
    return dp[n][m]
}

10_solution2_memo.go

package dp

func isMatch(s string, p string) bool {
    n, m := len(s), len(p)
    dp := make([][]int, n+1) // -1 = not computed, 0 = false, 1 = true
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    matches := func(i, j int) bool { // s[i-1] vs p[j-1]
        return p[j-1] == '.' || s[i-1] == p[j-1]
    }

    var f func(i, j int) bool
    f = func(i, j int) bool {
        if j == 0 {
            return i == 0 // empty pattern matches only empty s
        }
        if dp[i][j] != -1 {
            return dp[i][j] == 1
        }

        var res bool
        if p[j-1] == '*' {
            res = f(i, j-2) // zero copies
            if !res && i > 0 && matches(i, j-1) {
                res = f(i-1, j) // one more copy
            }
        } else {
            res = i > 0 && matches(i, j) && f(i-1, j-1)
        }

        dp[i][j] = 0
        if res {
            dp[i][j] = 1
        }
        return res
    }

    return f(n, m)
}

10_solution1_tab.java

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]; // zero copies
                    if (i > 0 && matches(s, p, i, j - 1))
                        dp[i][j] = dp[i][j] || dp[i - 1][j]; // one more copy
                } else {
                    dp[i][j] = i > 0 && matches(s, p, i, j) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }

    private boolean matches(String s, String p, int i, int j) { // s[i-1] vs p[j-1]
        return p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1);
    }
}

10_solution2_memo.java

class Solution {
    private Boolean[][] dp; // null = not computed

    private boolean matches(String s, String p, int i, int j) { // s[i-1] vs p[j-1]
        return p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1);
    }

    private boolean f(int i, int j, String s, String p) {
        if (j == 0)
            return i == 0; // empty pattern matches only empty s
        if (dp[i][j] != null)
            return dp[i][j];

        boolean res;
        if (p.charAt(j - 1) == '*') {
            res = f(i, j - 2, s, p); // zero copies
            if (!res && i > 0 && matches(s, p, i, j - 1))
                res = f(i - 1, j, s, p); // one more copy
        } else {
            res = i > 0 && matches(s, p, i, j) && f(i - 1, j - 1, s, p);
        }
        return dp[i][j] = res;
    }

    public boolean isMatch(String s, String p) {
        dp = new Boolean[s.length() + 1][p.length() + 1];
        return f(s.length(), p.length(), s, p);
    }
}

10_solution1_tab.js

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  const n = s.length, m = p.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(false));
  dp[0][0] = true;

  const matches = (i, j) => p[j - 1] === '.' || s[i - 1] === p[j - 1]; // s[i-1] vs p[j-1]

  for (let i = 0; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 2]; // zero copies
        if (i > 0 && matches(i, j - 1)) dp[i][j] = dp[i][j] || dp[i - 1][j]; // one more copy
      } else {
        dp[i][j] = i > 0 && matches(i, j) && dp[i - 1][j - 1];
      }
    }
  }
  return dp[n][m];
};

10_solution2_memo.js

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  const n = s.length, m = p.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));

  const matches = (i, j) => p[j - 1] === '.' || s[i - 1] === p[j - 1]; // s[i-1] vs p[j-1]

  const f = (i, j) => {
    if (j === 0) return i === 0; // empty pattern matches only empty s
    if (dp[i][j] !== -1) return dp[i][j];

    let res;
    if (p[j - 1] === '*') {
      res = f(i, j - 2); // zero copies
      if (!res && i > 0 && matches(i, j - 1)) res = f(i - 1, j); // one more copy
    } else {
      res = i > 0 && matches(i, j) && f(i - 1, j - 1);
    }
    return (dp[i][j] = res);
  };

  return f(n, m);
};

10_solution1_tab.py

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True

        def matches(i: int, j: int) -> bool:  # s[i-1] vs p[j-1]
            return p[j - 1] == "." or s[i - 1] == p[j - 1]

        for i in range(n + 1):
            for j in range(1, m + 1):
                if p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 2]  # zero copies
                    if i > 0 and matches(i, j - 1):
                        dp[i][j] = dp[i][j] or dp[i - 1][j]  # one more copy
                else:
                    dp[i][j] = i > 0 and matches(i, j) and dp[i - 1][j - 1]
        return dp[n][m]

10_solution2_memo.py

from typing import List, Optional


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp: List[List[Optional[bool]]] = [[None] * (m + 1) for _ in range(n + 1)]

        def matches(i: int, j: int) -> bool:  # s[i-1] vs p[j-1]
            return p[j - 1] == "." or s[i - 1] == p[j - 1]

        def f(i: int, j: int) -> bool:
            if j == 0:
                return i == 0  # empty pattern matches only empty s
            if dp[i][j] is not None:
                return dp[i][j]

            if p[j - 1] == "*":
                res = f(i, j - 2)  # zero copies
                if not res and i > 0 and matches(i, j - 1):
                    res = f(i - 1, j)  # one more copy
            else:
                res = i > 0 and matches(i, j) and f(i - 1, j - 1)

            dp[i][j] = res
            return res

        return f(n, m)

10_solution1_tab.rs

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let (s, p) = (s.as_bytes(), p.as_bytes());
        let (n, m) = (s.len(), p.len());
        let mut dp = vec![vec![false; m + 1]; n + 1];
        dp[0][0] = true;

        let matches = |i: usize, j: usize| p[j - 1] == b'.' || s[i - 1] == p[j - 1]; // s[i-1] vs p[j-1]

        for i in 0..=n {
            for j in 1..=m {
                if p[j - 1] == b'*' {
                    dp[i][j] = dp[i][j - 2]; // zero copies
                    if i > 0 && matches(i, j - 1) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j]; // one more copy
                    }
                } else {
                    dp[i][j] = i > 0 && matches(i, j) && dp[i - 1][j - 1];
                }
            }
        }
        dp[n][m]
    }
}

10_solution2_memo.rs

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let (s, p) = (s.as_bytes(), p.as_bytes());
        let mut dp = vec![vec![None; p.len() + 1]; s.len() + 1]; // None = not computed
        Self::f(s.len(), p.len(), s, p, &mut dp)
    }

    fn matches(s: &[u8], p: &[u8], i: usize, j: usize) -> bool {
        // s[i-1] vs p[j-1]
        p[j - 1] == b'.' || s[i - 1] == p[j - 1]
    }

    fn f(i: usize, j: usize, s: &[u8], p: &[u8], dp: &mut Vec<Vec<Option<bool>>>) -> bool {
        if j == 0 {
            return i == 0; // empty pattern matches only empty s
        }
        if let Some(res) = dp[i][j] {
            return res;
        }

        let res = if p[j - 1] == b'*' {
            // zero copies, or one more copy
            Self::f(i, j - 2, s, p, dp)
                || (i > 0 && Self::matches(s, p, i, j - 1) && Self::f(i - 1, j, s, p, dp))
        } else {
            i > 0 && Self::matches(s, p, i, j) && Self::f(i - 1, j - 1, s, p, dp)
        };

        dp[i][j] = Some(res);
        res
    }
}