Python의 와일드카드 일치

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

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

• 별표 '*'는 0개 이상의 문자와 일치합니다.

예를 들어 입력이 s ="aa" 및 p ="a?"와 같으면 동일한 입력 문자열에 대해 참이 되고 패턴이 "?*"이면 참이 됩니다.

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

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

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

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

• 범위 1에서 ps −

  에 있는 i의 경우

  • p[i] =별이면

    • dp[0, i] :=dp[0, i - 1]

• 범위 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 – 1, j] 및 dp[i, j – 1]의 최대값

• 반환 dp[ss, ps]

예제(파이썬)

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

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

입력

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

출력

True
True