โปรแกรมตรวจสอบรูปแบบนิพจน์ทั่วไปว่าตรงกับสตริงหรือไม่ในPython

สมมติว่าเรามีสตริง s และรูปแบบนิพจน์ทั่วไป เราต้องตรวจสอบว่ารูปแบบที่กำหนดตรงกับสตริงที่กำหนดหรือไม่ ในนิพจน์ทั่วไป มีกฎอยู่สองสามข้อ -

• . (จุด) ซึ่งตรงกับอักขระตัวใดตัวหนึ่ง

• * (ดอกจัน) ซึ่งตรงกับศูนย์หรือมากกว่าองค์ประกอบก่อนหน้า

ดังนั้น หากอินพุตเหมือน pattern ="h.l*o" s ="hello" ผลลัพธ์จะเป็น True เนื่องจากเรามี ra และอักขระตัวเดียว

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

• n :=ขนาดของ s

• m :=ขนาดของ p

• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j

• ถ้า j เท่ากับ m แล้ว

  • กลับฉันเหมือนกับ n

• ตรงกัน :=จริงเมื่อ (i

• ถ้า j + 1 &m และ p[j + 1] เหมือนกับ "*" ดังนั้น

  • คืนค่าจริงเมื่อ dp(i, j + 2) หรือ (จับคู่และ dp (i + 1, j)) มิฉะนั้นเป็นเท็จ

• คืนค่าการแข่งขันและ dp(i + 1, j + 1)

• จากวิธีหลักส่งคืน dp(0, 0)

ตัวอย่าง

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

class Solution:
   def solve(self, p, s):
      n = len(s)
      m = len(p)
      def dp(i, j):
         if j == m:
            return i == n
         match = i < n and (s[i] == p[j] or p[j] == ".")
         if j + 1 < m and p[j + 1] == "*":
            return dp(i, j + 2) or (match and dp(i + 1, j))
         return match and dp(i + 1, j + 1)
      return dp(0, 0)
ob = Solution()
pattern = "h.l*o"
s = "hello"
print(ob.solve(pattern, s))

อินพุต

"h.l*o", "hello"

ผลลัพธ์

True