# 10. Regular Expression Matching

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: bool isMatch(string s, string p) { const int m = s.length(); const int n = p.length(); // dp[i][j] := true if s[0..i) matches p[0..j) vector> dp(m + 1, vector(n + 1)); dp[0][0] = true; auto isMatch = [&](int i, int j) -> bool { return j >= 0 && p[j] == '.' || s[i] == p[j]; }; for (int j = 0; j < p.length(); ++j) if (p[j] == '*' && dp[0][j - 1]) dp[0][j + 1] = true; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (p[j] == '*') { const bool noRepeat = dp[i + 1][j - 1]; // Min index of '*' is 1 const bool doRepeat = isMatch(i, j - 1) && dp[i][j + 1]; dp[i + 1][j + 1] = noRepeat || doRepeat; } else if (isMatch(i, j)) { dp[i + 1][j + 1] = dp[i][j]; } return dp[m][n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public boolean isMatch(String s, String p) { final int m = s.length(); final int n = p.length(); // dp[i][j] := true if s[0..i) matches p[0..j) boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int j = 0; j < p.length(); ++j) if (p.charAt(j) == '*' && dp[0][j - 1]) dp[0][j + 1] = true; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (p.charAt(j) == '*') { final boolean noRepeat = dp[i + 1][j - 1]; // Min index of '*' is 1 final boolean doRepeat = isMatch(s, i, p, j - 1) && dp[i][j + 1]; dp[i + 1][j + 1] = noRepeat || doRepeat; } else if (isMatch(s, i, p, j)) { dp[i + 1][j + 1] = dp[i][j]; } return dp[m][n]; } private boolean isMatch(final String s, int i, final String p, int j) { return j >= 0 && p.charAt(j) == '.' || s.charAt(i) == p.charAt(j); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution: def isMatch(self, s: str, p: str) -> bool: m = len(s) n = len(p) # dp[i][j] := True if s[0..i) matches p[0..j) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True def isMatch(i: int, j: int) -> bool: return j >= 0 and p[j] == '.' or s[i] == p[j] for j, c in enumerate(p): if c == '*' and dp[0][j - 1]: dp[0][j + 1] = True for i in range(m): for j in range(n): if p[j] == '*': noRepeat = dp[i + 1][j - 1] # Min index of '*' is 1 doRepeat = isMatch(i, j - 1) and dp[i][j + 1] dp[i + 1][j + 1] = noRepeat or doRepeat elif isMatch(i, j): dp[i + 1][j + 1] = dp[i][j] return dp[m][n]