input :
- s, p
output :
- p를 통해 s의 문자열의 매칭 여부를 출력하시오
조건 :
- "*"의 경우 어떠한 문자든, 여러개에 매칭 가능
- "?"의 경우 1개의 어떠한 문자든 매칭 가능
Solution explain : Solution1
idea
-
재귀를 통해서 짠다면 특정 s_idx, p_idx에서 할 수 있는 행동은 3가지이다.
(s_idx + 1. p_idx), (s_idx. p_idx + 1), (s_idx + 1. p_idx + 1) -
그러나 이를 재귀로 한다면 3^2000.... 심하다...
-
언제나 그렇듯 재귀로 할 수 있는 경우의 수를 만들었으면 DP로 만들어야 해결이 가능하다.
-
row, col의 의미부터 정하자. row == p를 이루는 각 문자들, col == s를 이루는 각 문자들.
-
dp[i][j]의 의미는 p[0 ~ i], s[0 ~ j]가 매칭이 되었는지 여부를 담고 있다.
-
만약 s_char, p_char가 동일하다. 혹은 p_char이 "?"인 경우에는 (s_idx + 1. p_idx + 1)의 행동을 하기 위해 역으로
(s_idx - 1. p_idx - 1)의 값을 가져온다. -
현재 위치 이전에도 매칭이 되었다면 매칭이 여전히 될 것이고, 그렇지 않으면 매칭이 안 될 것이다.
-
나머지 2가지 행동은 패턴이 "*"인 경우에 수행을 한다.
-
이 때도 역으로
(s_idx - 1. p_idx), (s_idx. p_idx - 1)을 수행하는데 이 의미는 -
p_idx - 1 : 의 경우 패턴을 계속 늘려도 s와 매칭이 가능하냐는 의미이다. "*"의 경우에는
s = zzzde, p = ???de*일 때 *이 더 추가되어도 True가 된다.
(s_idx == 4, p_idx == 4)일 때의 값을 (s_idx == 4, p_idx == 5), (s_idx == 4, p_idx == 6)일 때도 가져와야 한다는 의미가. 된다. -
s_idx - 1 : 의 경우 현재 패턴에 s의 길이가 더 늘어나도 괜찮냐는 의미가 된다.
주의
- 행동의 의미 이해 하기 너무 어렵다..
class Solution:
def isMatch(self, s: str, p: str) -> bool:
length_s, length_p = len(s), len(p)
dp = [[0] * (length_s + 1) for _ in range(length_p + 1)]
dp[0][0] = 1
for i in range(1, length_p + 1):
if p[i - 1] != "*":
break
dp[i][0] = 1
for p_idx in range(1, length_p + 1):
for s_idx in range(1, length_s + 1):
p_val, s_val = p[p_idx - 1], s[s_idx - 1]
dp[p_idx][s_idx] = 0
if p_val == s_val or p_val == "?":
dp[p_idx][s_idx] = dp[p_idx - 1][s_idx - 1]
continue
if p_val == "*":
dp[p_idx][s_idx] = dp[p_idx - 1][s_idx] or dp[p_idx][s_idx - 1]
return dp[-1][-1]