난이도 - Hard
Intuition
1) Recursion (Time Limit Exceeded)
이 문제는 recursion을 통해 글자를 확인하면서 풀 수 있다. 하지만 time limit exceeded가 뜨므로 다른 방법을 생각해내야 한다.
1. 만약 p가 없다면, 패턴확인이 다 끝난 것이므로 s가 또한 없으면 True, 아니면 False를 반환한다.
2. 처음글자를 확인한다. 만약 s가 있으면서 p의 첫글자와 같거나, p의 첫글자가 "."이면, True로 설정해 놓는다. first_match라는 변수에 저장해놓는다.
3. p의 길이가 2 이상이고 p의 두번째 글자가 "*"이면, first_match가 True이면 s[1:]를 통해 다시 recursion을 하고, first_match가 False이면 s는 그대로 하고 p[2:]로 해서 다음 패턴을 찾는다.
4. 만약 p의 길이가 2 이상이고 p의 두번째 글자가 "*"이 아니면, first_match가 맞으면서 s[1:]와 p[1:]를 recursion하면서 다음 글자의 패턴을 확인해간다.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p:
return not s
first_match = bool(s) and p[0] in {s[0], "."}
if len(p) >= 2 and p[1] == "*":
return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
else:
return first_match and self.isMatch(s[1:], p[1:])Time Complexity: O((T+P)^(2^(T+P/2))) 여기서 T,P는 각각 s와 p의 길이이다.
Space Complexity: O((T+P)^(2^(T+P/2)))
2) DP
우리는 dp(i, j)가 s[i:] 와 p[j:]의 match의 결과를 담고 있다는 걸로 dynamic programming방법을 생각할 수 있다.
1. 우리는 dp(i, j)가, 즉 s[i:] 와 p[j:]의 match가 True인지 False인지 알고 싶다.
2.1 Top-Down의 경우
- 먼저 memo에 (i,j)의 결과가 있는지부터 확인한다, 있으면 그 값을 반환하고, 아니면 계산을 해야 한다.
- j가 len(p)인지, 즉 패턴확인이 다 끝났는지 확인한다. 패턴확인이 다 끝났는데도 i가 len(s)가 아니면 확인해야할 s가 있다는 것이므로 패턴에 맞지 않으니 False를 반환, 아니면 True를 반환해야 한다.
- 만약 j가 아직 len(p)가 되지 않아서 패턴확인이 더 필요하면, p[j]가 s[i]인지 아니면 "."인지 확인해서 첫번째 글자가 맞는지 확인한다. 이 값을 first_match에 저장한다.
- 만약 p[j+1] 이 "*"이었다면, 우리는 2가지를 확인해야 한다. 이 "*"를 무시하고 p[j+2]부터 다시 패턴을 확인하던지, 아니면 현재 p[j]가 s[i]혹은 "."이므로 패턴이 만족이 되서 p[j]는 그대로 두고 s[i+1]부터 패턴을 확인하던지. 둘 중 하나라도 True이면 이 값은 True이다.
- 만약 p[j+1]이 "*"이 아니면, 우리는 현재 글자만 확인해야한다. 따라서 first_match이면서 s[i+1]이 p[j+1]패턴에 맞는지 확인해야 한다.
- 구한 (i, j)에서의 값을 memo[i, j]값에 넣는다.
2.2 Bottom-Up의 경우
- 먼저 dp를 len(s) +1 x len(p) + 1 matrix로 만들고 False로 초기화 한다. dp[-1][-1] 은 True로 설정해서 시작지점을 만든다.
- i는 len(s)부터 0까지, j는 len(p) - 1부터 0까지 for문으로 돌린다.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Top-Down
memo = {}
def dp(i: int, j: int) -> bool:
if (i, j) not in memo:
if j == len(p):
ans = i == len(s)
else:
first_match = i < len(s) and p[j] in {s[i], "."}
if j + 1 < len(p) and p[j+1] == "*":
ans = dp(i, j + 2) or (first_match and dp(i+1, j))
else:
ans = first_match and dp(i+1, j+1)
memo[i, j] = ans
return memo[i, j]
return dp(0, 0)
# Bottom-Up
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[-1][-1] = True
for i in range(len(s), -1, -1):
for j in range(len(p) - 1, -1, -1):
first_match = i < len(s) and p[j] in {s[i], "."}
if j + 1 < len(p) and p[j+1] == "*":
dp[i][j] = dp[i][j+2] or (first_match and dp[i+1][j])
else:
dp[i][j] = first_match and dp[i+1][j+1]
print(dp)
return dp[0][0]
Time Complexity: O(TP) 우리는 dp를 통해서 dp(i, j), i = 0, ..., T; j = 0, ..., P까지 돌리기 때문이다.
Space Complexity: O(TP) 우리는 dp를 통해서 O(TP)만큼의 결과를 저장해 놔야 한다.