[leetcode-10] Regular Expression Matching

LeetCode-10

Regular Expression Matching : Given an input string s and a pattern p, implement regular expression matching

note : The matching should cover the entire input string (not partial).

Answer

        :::python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(re.findall(p,s))>0:
            return s == re.findall(p,s)[0]
        else:
            return False

Result : 201ms Memory: 13.9mb

Solve

        :::python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i, j = len(s) - 1, len(p) - 1
        return self.backtrack({}, s, p, i, j)
    def backtrack(self, cache, s, p, i, j):
        key = (i, j)
        if key in cache:
            return cache[key]
        if i == -1 and j == -1:
            cache[key] = True
            return True
        if i != -1 and j == -1:
            cache[key] = False
            return cache[key]
        if i == -1 and p[j] == '':
            k = j
            while k != -1 and p[k] == '':
                k -= 2
            if k == -1:
                cache[key] = True
                return cache[key]
            cache[key] = False
            return cache[key]
        if i == -1 and p[j] != '':
            cache[key] = False
            return cache[key]
        if p[j] == '':
            if self.backtrack(cache, s, p, i, j - 2):
                cache[key] = True
                return cache[key]
            if p[j - 1] == s[i] or p[j - 1] == '.':
                if self.backtrack(cache, s, p, i - 1, j):
                    cache[key] = True
                    return cache[key]
        if p[j] == '.' or s[i] == p[j]:
            if self.backtrack(cache, s, p, i - 1, j - 1):
                cache[key] = True
                return cache[key]
        cache[key] = False
        return cache[key]

Result : 198ms Memory: 14mb

정규식은 문자열 패턴을 지정하는 데 사용되는 문자열이며, Python 및 다른 프로그래밍 언어에서 사용됩니다. 문자열의 일부 또는 전체와 일치하는 패턴을 찾을 수 있습니다.

정규식은 문자, 메타 문자 및 특수 문자의 조합으로 표현됩니다. 메타 문자는 특별한 의미가 있으며 특수 문자는 문자 그대로 해석됩니다. 예를 들어, "a"는 문자 a와 정확히 일치하고 "."은 어떤 문자와 일치합니다.

Regular Expression Matching은 문자열이 정규식 패턴과 일치하는지 여부를 확인하는 프로세스입니다. 이를 수행하는 가장 일반적인 방법은 re 모듈을 사용하는 것입니다. re 모듈은 정규식을 패턴으로 사용하여 문자열을 처리하고 일치하는 패턴을 찾을 수 있습니다.

간단한 예로, "hello"와 일치하는 문자열을 찾으려면 패턴 "hello"를 사용할 수 있습니다. 또 다른 예로, 패턴 "[a-z]+"는 문자열과 일치하는 모든 소문자 알파벳을 포함합니다.

정규식으로 문자열을 처리하면 문자열에서 특정 패턴을 찾을 수 있습니다. 이를 활용해 문자열에서 특정 단어나 매치되는 문자열을 찾거나 패턴에 맞는 문자열을 대체하거나 추출할 수 있습니다.