10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

C++

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

        dp[0][0] = true;
        for  (int j = 2; j <= n; j++) {
            dp[0][j] = dp[0][j-2] && p[j - 1] == '*';
        }

        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.'));
                }
            }
        }

        return dp[m][n];
    }
};

Go

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

  dp[0][0] = true
  for j := 2; j <= n; j++ {
    dp[0][j] = dp[0][j-2] && p[j-1] == '*'
  }
  for j := 1; j <= n; j++ {
    for i := 1; i <= m; i++ {
      if p[j-1] == '.' || p[j-1] == s[i-1] {
        dp[i][j] = dp[i-1][j-1]
      } else if p[j-1] == '*' {
        dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j-2] == s[i-1] || p[j-2] == '.'))
      }
    }
  }

  return dp[m][n]
}

JavaScript

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

  dp[0][0] = true
  for (let j = 2; j <= n; j++) {
    dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'
  }

  for (let j = 1; j <= n; j++) {
    for (let i = 1; i <= m; i++) {
      if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else if (p[j - 1] == '*') {
        dp[i][j] = dp[i - 1][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.'))
      }
    }
  }

  return dp[m][n]
};

Python

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m, n = len(s), len(p)
        dp = [[False for j in range(n + 1)] for i in range(m + 1)]
        dp[0][0] = True
        for j in range(2, n + 1):
            dp[i][j] = dp[i][j - 2] and p[j - 1] == '*'
        for j in range(1, n + 1):
            for i in range(1, m + 1):
                if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j - 2] or (dp[i  -1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.'))
        return dp[m][n]