알고리즘/leetcode

[leetcode] 10. Regular Expression Matching

implement 2024. 1. 6. 00:00
728x90

문제이해

문자열 s와 p가 주어질 때, s가 p의 정규식에 맞는지 확인하는 문제이다.

'.'은 s의 하나의 문자와 매칭이 되면 되고, '*'은 '*' 이전의 문자가 0개 또는 1개 이상의 문자열이 반복됨을 뜻한다.

s와 p는 영어 소문자만 입력되고, p는 '.'과 '*'까지 입력된다.

계획

얼핏 보면 s와 p를 순회하며 문자를 하나하나 매칭해 나가면 되는 문제처럼 보이지만, '.'과 '*'의 조합 때문에 불가능하다. '.'뒤에 '*'이 온다면 s에서 어떤 문자가 얼만큼 반복될지 순회하는 도중에는 알 수 없기 때문에 계속해서 현재 해당하는 문자열을 비교하고, 뒤에 문자열이 정규식에 맞는지 안 맞는지를 파악해야 한다. 

예를 들면, s = "aaaaab", p = "a*aab" 이나 s = "abcd", p = "ap*p*p*b.*" 와 같은 예시가 문제를 어렵게 하는 것 같다.

비교하고자 하는 문자열과 그 뒤의 문자열을 비교하며 참인지 거짓인지 판단하는 문제고, s와 p의 길이가 최대 20으로 많지 않으므로, 재귀를 활용하면 좋을 것 같다. s의 인덱스 i와 p의 인덱스 j가 있고, s와 p의 인덱스의 뒤의 문자열에 대해 정규식을 판단하는 함수 match가 있다고 가정할때 s가 p의 정규식에 맞는 지 확인하는 식을 간단히 세우면 다음과 같다.

def match(i, j) :
	...
	return (s[i] == p[j] || p[j] == '.') && match(i+1, j+1)
	...

현재 인덱스가 맞거나 p가 '.'일때 그 뒤의 인덱스도 맞는지 비교한다. 그런데 문제가 생긴다. p[j+1] == '*' 일 때,  s[i+1]와 p[j+1]는 같지 않더라도 뒤에 어떤 문자가 오는지에 따라 s와 p는 같을 수 있기 때문이다. 따라서, '*'이 있는 경우에는 다르게 비교해 줘야 한다. p[j+1]에 '*'이 있을 때, s는 다음과 같은 경우에 참이다.

i. p[j]의 문자가 s에서 0개 반복될 때
ii. p[j]의 문자가 s에서 1개 이상 반복될 때

따라서 모든 경우를 생각한다면, 뒤에 '*'이 있을 때와 없을 때, 있다면 문자가 0개 반복되는지 여러 개 반복되는지를 비교를 해준다면 s가 p의 정규식에 해당하는지 확인할 수 있다.

 

계획수행

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def match(sidx, pidx):
            if pidx == len(p):
                return sidx == len(s)		#p가 끝까지 같을때 s도 끝까지 안같다면 거짓이다.
            
            first = sidx < len(s) and (s[sidx] == p[pidx] or p[pidx] == '.')
            #sidx가 len(s)와 같다면 비교할 수 없으므로 거짓이다.

            if pidx + 1 < len(p) and p[pidx+1] == '*':	#뒤에가 '*'인 경우
                return (first and match(sidx+1, pidx)) or match(sidx, pidx+2)
                #p[pidx]에 있는 문자가 1개 이상 반목되는 경우 or (0개 반복되는 경우 or 더이상 반복되지 않는 경우)
            else:			#뒤에가 '*'이 아닌 경우
                return first and match(sidx + 1, pidx + 1)
        
        return match(0, 0)

 

그런데 이 코드에서는 조금 더 최적화할 수 있는 부분이 있다. 

'*'이 있어서

ans = (first and match(sidx+1, pidx)) or match(sidx, pidx+2)

를 수행한 경우, 다음 인덱스를 비교할 때 이미 비교했던 인덱스를 다시 연산할 수 있는 경우가 생긴다. 따라서 동적 계획법을 이용하여 memo라는 딕셔너리에 이미 연산한 결과를 저장하고, memo를 먼저 확인 후 없다면 연산을 할 수 있도록 한다면 더 효율적으로 계산할 수 있다.

따라서, 정답 코드는 이렇다.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo={}

        def match(sidx, pidx):
            if (sidx, pidx) in memo:
                return memo[(sidx, pidx)]
            
            if pidx == len(p):
                return sidx == len(s)
            
            first = sidx < len(s) and (s[sidx] == p[pidx] or p[pidx] == '.')

            if pidx + 1 < len(p) and p[pidx+1] == '*':
                ans = (first and match(sidx+1, pidx)) or match(sidx, pidx+2)
            else:
                ans =  first and match(sidx + 1, pidx + 1)
            
            memo[(sidx, pidx)] = ans
            return ans
        
        return match(0, 0)

 

느낀 점

문제를 오히려 어렵게 생각한 것이 문제를 못 풀게 하는 원인이 되었다. 그냥 처음 아이디어 그대로 코드를 작성하고 잘 최적화했다면 풀었을 텐데, 괜히 시간복잡도하고 공간복잡도 생각하느냐고 코드를 잘 작성하지 못했다. 앞으로 문제 풀 때는 시간복잡도, 공간복잡도 신경 쓰지 말고 푼다음, 최적화할 수 있는지 혹은 다른 접근법이 있는지 파악하는 순서로 문제를 풀어야겠다.

반응형