문자열 s와 정규식 패턴이 있다고 가정합니다. 주어진 패턴이 주어진 문자열과 일치하는지 여부를 확인해야 합니다. 정규식에는 규칙이 거의 없습니다 -
-
. 단일 문자와 일치하는 (마침표)
-
*(별표)는 선행 요소의 0개 이상과 일치합니다.
따라서 입력이 pattern ="h.l*o" s ="hello"와 같으면 ra와 단일 문자가 있으므로 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=s
의 크기 -
m :=p의 크기
-
dp() 함수를 정의합니다. 이것은 i, j가 걸릴 것입니다
-
j가 m과 같으면
-
리턴 i는 n과 동일합니다.
-
-
match :=(i
-
j + 1 &m 및 p[j + 1]이 "*"와 같으면
-
dp(i, j + 2) 또는 (match 및 dp(i + 1, j))일 때 true를 반환하고 그렇지 않으면 false
-
-
반환 일치 및 dp(i + 1, j + 1)
-
기본 메서드에서 dp(0, 0)
를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution: def solve(self, p, s): n = len(s) m = len(p) def dp(i, j): if j == m: return i == n match = i < n and (s[i] == p[j] or p[j] == ".") if j + 1 < m and p[j + 1] == "*": return dp(i, j + 2) or (match and dp(i + 1, j)) return match and dp(i + 1, j + 1) return dp(0, 0) ob = Solution() pattern = "h.l*o" s = "hello" print(ob.solve(pattern, s))
입력
"h.l*o", "hello"
출력
True