[LeetCode] 10. 정규 표현 식 일치 문제 풀이 보고서 (파 이 썬)

제목 분석:
이 문 제 는 간단 한 정규 표현 식 을 실현 하 는 것 입 니 다. '와' * '를 실현 해 야 합 니 다. 그 중에서' * '는 모든 문 자 를 표시 할 수 있 습 니 다.' * '는 앞의 문자 가 0 또는 임 의 로 나타 나 는 것 을 표시 합 니 다.먼저 욕심 을 부 리 는 방법 을 생각해 서 해결 해 야 하 는데 '.................................................................다른 방법 을 고려 하면 그 중에서 재 귀 는 바로 하나의 것 으로 문 제 를 하위 문제 로 나 누 어 고려 하 는 것 이다.일반적인 상황 에서 재 귀 는 동태 계획 으로 전환 할 수 있 고 동태 계획 은 공간 으로 시간 을 바 꿀 수 있다. 재 귀 시간 이 길 면 시간 제한 을 초과 할 수 있 기 때문에 우 리 는 동태 계획 으로 해결 하 는 것 도 고려 해 야 한다.
재 귀적 으로 문 제 를 해결 하 다.
생각:
1. p 가 비어 있 으 면 s 도 비어 있어 야 일치 합 니 다.
2. p 와 s 의 첫 번 째 문 자 를 비교 하고 표 시 를 합 니 다.
3. p [1] = '*' 는 두 가지 상황 으로 나 뉘 는데 '*' 를 앞의 문자 로 0 번 나타 나 면 p 두 글자 (하 나 는 '*') 를 건 너 뛰 고 재 귀적 으로 s 와 p [2:] 를 비교 합 니 다.'*' 를 이전 문자 로 한 번 나타 나 는 것 을 고려 하면 p 는 움 직 이지 않 지만 s 문 자 를 건 너 뛰 면 재 귀적 으로 s [1:] 와 p 를 비교 합 니 다.
4. 만약 p [1]! = '*'직접 재 귀 비교 s [1:] 와 p [1:].
재 귀적 코드 설명:
1. p 가 비어 있 으 면 s 도 비어 있어 야 일치 합 니 다.

if len(p) == 0: return len(s) == 0

2. s 와 p 의 첫 번 째 문자 가 같 는 지 비교 하고 표시 하 는 것 으로 간단하게 이해 할 수 있 습 니 다.

flag = len(s) != 0 and p[0] in {s[0], '.'}

3. p [1] = '*' 는 두 가지 상황 으로 나 뉘 는데 '*' 를 앞의 문자 로 0 번 나타 나 면 p 두 글자 (하 나 는 '*') 를 건 너 뛰 고 재 귀적 으로 s 와 p [2:] 를 비교 합 니 다.'*' 를 이전 문자 로 한 번 나타 나 는 것 을 고려 하면 p 는 움 직 이지 않 지만 s 문 자 를 건 너 뜁 니 다. 즉, 재 귀 비교 s [1:] 는 p, flag and 와 이전 문자 가 같 음 을 나타 냅 니 다.

        if len(p) >=2 and p[1] == '*':
            return (flag and self.isMatch(s[1:], p) or (self.isMatch(s, p[2:])))

4. 만약 p [1]! = '*'직접 재 귀적 비교 s [1:] 는 p [1:], flag and 와 이전 문자 가 같 음 을 나타 낸다.

        else:
            return flag and self.isMatch(s[1:], p[1:])

테스트 코드:

class Solution:
    def isMatch(self, s, p):
        if len(p) == 0: return len(s) == 0
        flag = len(s) != 0 and p[0] in {s[0], '.'}
        if len(p) >=2 and p[1] == '*':
            return (flag and self.isMatch(s[1:], p) or (self.isMatch(s, p[2:])))
        else:
            return flag and self.isMatch(s[1:], p[1:])


print(Solution().isMatch('aab','c*a*b'))#        

결과:
제출 표시: 런 타임: 1612 ms, Your runtime beats 7.13% of python 3 submissions. 운행 시간 이 비교적 길 면 대부분 사람들 이 재 귀적 으로 해결 하 는 것 이 아 닐 것 입 니 다. 동적 계획 을 사용 하여 공간 으로 시간 을 바 꾸 어 보 겠 습 니 다.
동적 계획 해결 문제:
동적 계획 코드 설명: 코드 해석 이 복잡 하기 때문에 저 는 코드 에 주석 을 직접 넣 었 습 니 다. 만약 에 제 가 참고 한 블 로 그 를 보 거나 디 버 깅 을 할 수 있 습 니 다.

class Solution:
    def isMatch(self, s, p):
        #      False     ，dp[i][j]    s[0->i]   p[0->j]    。
        dp=[[False for i in range(len(p)+1)] for j in range(len(s)+1)]
        #s  p        
        dp[0][0]=True
        # s      *       ，           *         
        for i in range(1,len(p)+1):
            dp[0][i] = p[i-1] == '*' and dp[0][i-2] and i>1

        for i in range(1,len(s)+1):
            for j in range(1,len(p)+1):
                #p   '*' ，        *           *      s      *         s       
                if p[j-1]=='*':
                    dp[i][j]=dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                #   *           and
                else:
                    dp[i][j] = dp[i-1][j-1] and (p[j-1] == '.' or p[j-1] == s[i-1])
        #  s[0->len(s)]   p[0->len(p)]   
        return dp[len(s)][len(p)]

print(Solution().isMatch("mississippi", ".*mis*is*p*."))#        

결과: 제출 표시: Runtime: 64ms, Your runtime beats 74.03% of python 3 submissions. 실행 시간 은 가능 합 니 다. 동적 계획 으로 문 제 를 해결 하 였 습 니 다.
참고 블 로그 1, 참고 블 로그 2