10. Regular Expression Matching

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

input :

• s, p
• s는 영어 소문자, p는 영어 소문자 + "." + "*"로 이루어져 있다.

output :

• s라는 문장을 p로 표현이 가능한지 출력하시오.

조건 :

• p로 문장 s가 나타나야 한다.
• "*"의 경우 앞에 존재하는 문자가 0개 혹은 여러 개 존재한다.

---

Solution explain : Solution1, Solution2

idea

주의

• base case의 경우 j == len(p)일 때, i == len(s)여야 한다. 구현을 보면 j == len(p)만으로 판단하는데 이는 i == len(s)를 조건에 추가하면 2번째 이동 조건을 수행 할 수 가 없다.

• 코드를 구현할 때 bool 연산의 경우 앞에 거를 우선적으로 하기에 lh and rh가 연산의 대상일 떄 lh가 True라면 rh를 수행하지 않는다. or연산이면 lh가 True라면 연산을 수행하지 않는다.

• 이를 바탕으로 코드의 and, or 연산을 수행해야 한다.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s, p = list(s), list(p)
        dp = dict()

        def recursive(i, j):
            if j == len(p):
                return i == len(s)
            if (i, j) in dp:
                return dp[(i, j)]

            # i == len(s)인 시점부터 matched는 false로 고정
            # 이걸 유지해서 밑에서 matched들이 먼저 false라 i를 키우는 재귀는 돌지 않음.
            # 그래서 23번째 줄의 j + 2 하는 재귀만 수행해서 답을 낸다.
            matched = i < len(s) and (s[i] == p[j] or p[j] == ".")

            if j + 1 < len(p) and p[j + 1] == "*":
                # matched의 경우 현재 "*"에 s의 문자를 걸리게 하고 넘어감.
                matched = matched and recursive(i + 1, j)

                # 아래의 recursive는 지금 "*"을 무시하고 현재 i를 유지하게 함.
                # 경우의 수가 2가지로 나뉘는 것을 모두 경험함.
                ret = recursive(i, j + 2) or matched
            else:
                ret = matched and recursive(i + 1, j + 1)
            dp[(i, j)] = ret
            return dp[(i, j)]

        return recursive(0, 0)

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

        dp[0][0] = 1
        for j in range(1, len_p + 1):
            cha_p = p[j - 1]
            if cha_p == "*":
                dp[j][0] = dp[j - 2][0]

        for i in range(1, len_p + 1):
            for j in range(1, len_s + 1):
                cha_p, cha_s = p[i - 1], s[j - 1]

                if cha_p == "*":
                    prev_p = p[i - 2]
                    dp[i][j] = dp[i - 2][j] or ((cha_s == prev_p or prev_p == ".") and dp[i][j - 1])
                else:
                    dp[i][j] = dp[i - 1][j - 1] and (cha_s == cha_p or cha_p == ".")


        return dp[i][j] == 1