Regular Expression Matching

Problem Id: 10 Difficulty: Hard Tag: String Tag: Dynamic Programming Tag: Backtracking


Intuition

Use dynamic programming to solve this problem.

1. Define a status dp[i][j]. If dp[i][j] == True, s[:i] matches p[:j].

  1. The recurrence formular depends on p[j] and p[j + 1].
    • If p[j + 1] != '*', dp[i][j] = dp[i - 1][j - 1] and (s[i] == p[j] or p[j] == '.'
    • If p[j + 1] == '*',
      • If p[j] == '.', dp[i][j + 1] = True if there exists any k where dp[k][j - 1] == True
      • If p[j] != '.', dp[i][j + 1] = True if there exists any k where dp[k][j - 1] == True and characters in s[k + 1: i + 1] are all p[j].
  2. Then we could use the recurrence formular to solve the problem from down to top.

Here I uses a skill. Since all '*' are only used to match multiple times of an existing character, we could combime it with the previous character and treat them as a single character.

Solution


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # Pre-format p to generate a list and combine '*' with previous
        # character.
        pattern = []
        index = 0
        while index < len(p):
            if index + 1 < len(p) and p[index + 1] == '*':
                pattern.append(p[index:index + 2])
                index += 2
            else:
                pattern.append(p[index])
                index += 1

        # Init dp status storage
        dp = [[False] * (len(pattern) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True

        # Bottom-up solve dp problem
        for i in range(len(s) + 1):
            for j in range(1, len(pattern) + 1):
                if len(pattern[j - 1]) == 1:
                    if i > 0:
                        dp[i][j] = dp[i - 1][j - 1] and (pattern[j - 1] == '.' or s[i - 1] == pattern[j - 1])
                else:
                    if pattern[j - 1][0] == '.':
                        dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
                    else:
                        dp[i][j] = dp[i][j - 1] or (dp[i - 1][j] and s[i - 1] == pattern[j - 1][0])

        return dp[-1][-1]