การจับคู่สัญลักษณ์แทนใน Python

สมมติว่าเรามีสตริงอินพุต s และสตริงอินพุตอื่น p นี่คือสตริงหลักและ p คือรูปแบบ เราต้องกำหนดวิธีหนึ่งวิธีที่สามารถจับคู่รูปแบบในสตริงได้ ดังนั้นเราจึงต้องใช้สิ่งนี้สำหรับนิพจน์ทั่วไปที่รองรับอักขระตัวแทนเช่น '?' และ '*'

• Dot '?' จับคู่อักขระตัวเดียว

• ดาว '*' จับคู่อักขระตั้งแต่ 0 ตัวขึ้นไป

ตัวอย่างเช่น หากอินพุตเป็น s =“aa” และ p =“a?” ก็จะเป็นจริงสำหรับสตริงอินพุตเดียวกัน หาก Patter เป็น “?*” ก็จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ss :=ขนาดของ s และ ps :=ขนาดของ p

• ทำให้ dp เป็นเมทริกซ์ขนาด ss x ps และเติมโดยใช้ค่าเท็จ

• อัปเดต p และ s โดยเพิ่มช่องว่างก่อนหน้าสิ่งเหล่านี้

• สำหรับฉันอยู่ในช่วง 1 ถึง ps −

  • ถ้า p[i] =ดาว แล้ว

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

• สำหรับผมอยู่ในช่วง 1 ถึง ss

  • สำหรับ j ในช่วง 1 ถึง ps

    • ถ้า 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]

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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