Python의 정규 표현식 일치

입력 문자열 s와 다른 입력 문자열 p가 있다고 가정합니다. 여기서 s는 기본 문자열이고 p는 패턴입니다. 문자열의 패턴과 일치할 수 있는 하나의 메서드를 정의해야 합니다. 따라서 '.' 및 '*'를 지원하는 정규식에 대해 이것을 구현해야 합니다.

• 점 '.' 단일 문자와 일치

• 별표 '*' 선행 요소의 0개 이상과 일치합니다.

예를 들어 입력이 s ="aa" 및 p ="a."와 같은 경우 동일한 입력 문자열에 대해 패턴이 ".*"이면 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ss :=s의 크기 및 ps :=p의 크기

• dp를 ss x ps 크기의 행렬로 만들고 false 값을 사용하여 채웁니다.

• 이들 앞에 공백 하나를 추가하여 p와 s를 업데이트하십시오.

• 범위 2에서 ps −

  에 있는 i의 경우

  • dp[0, i] :=dp[0, i - 2] p[i]가 별표일 때, 그렇지 않으면 False

• 범위 1에서 ss까지의 i에 대해

  • 범위 1에서 ps까지의 j에 대해

    • s[i]가 p[j]이거나 p[j]가 점이면

      • dp[i, j] :=dp[i – 1, j – 1]

    • 그렇지 않으면 p[j]가 별표일 때

      • dp[i, j] :=dp[i, j - 2]

      • s[i]가 p[j – 1]이거나 p[j – 1]이 점이면

        • dp[i, j] :=dp[i, j] 및 dp[i – 1, j]

          의 최대값

• 반환 dp[ss, ps]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def isMatch(self, s, p):
      ss = len(s)
      ps = len(p)
      dp = [[False for i in range(ps+1)] for j in range(ss+1)]
      p = " "+p
      s = " " + s
      dp[0][0]=True
      for i in range(2,ps+1):
         dp[0][i] = dp[0][i-2] if p[i]=='*'else False
      for i in range(1,ss+1):
         for j in range(1,ps+1):
            if s[i] ==p[j] or p[j]=='.':
               dp[i][j]= dp[i-1][j-1]
            elif p[j] == '*':
               dp[i][j] = dp[i][j-2]
               if s[i] == p[j-1] or p[j-1]=='.':
                  dp[i][j] = max(dp[i][j],dp[i-1][j])
      return dp[ss][ps]
ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*"))

입력

"aa", "a."
"aaaaaa", "a*"

출력

True
True