การจับคู่นิพจน์ปกติใน Python

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

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

• ดาว '*' จับคู่ 0 หรือมากกว่าขององค์ประกอบก่อนหน้า

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

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

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

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

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

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

  • dp[0, i] :=dp[0, i - 2] เมื่อ p[i] เป็นดาว มิฉะนั้น เป็นเท็จ

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

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

    • ถ้า s[i] คือ p[j] หรือ p[j] คือ dot แล้ว

      • 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