ได้รับสตริง s และพาตเทิร์น p ต้องตรวจสอบว่า p ตรงกับ s หรือไม่ พาตเทิร์นรองรับ:
.(จุด) = ตรงกับตัวอักษรใดๆ หนึ่งตัว*(ดาว) = ตรงกับศูนย์หรือหลายตัวของอิลิเมนต์ก่อนหน้า
ตัวอย่าง
Pattern: "h.l*o", String: "hello" → True
เพราะ h ตรง h, . ตรง e, l* ตรง ll, o ตรง o
แนวทางแก้ปัญหา
ใช้ Recursive DP with Memoization (Top-down):
- ฟังก์ชัน
dp(i, j)= พาตเทิร์นp[j:]ตรงกับสตริงs[i:]หรือไม่ - Base case:
j == len(p)→ ต้องมีi == len(s) - ถ้าตัวถัดไปคือ
*: สองทางเลือก- ข้าม
x*ไปเลย →dp(i, j+2) - ใช้
x*จับคู่ตัวอักษรปัจจุบัน (ถ้าตรง) →dp(i+1, j)
- ข้าม
- ถ้าไม่มี
*: ต้องจับคู่ตัวปัจจุบัน แล้วไปdp(i+1, j+1)
การใช้งาน (Python)
class Solution:
def solve(self, p, s):
n, m = len(s), len(p)
from functools import lru_cache
@lru_cache(None)
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()
print(ob.solve("h.l*o", "hello")) # Output: True
ความซับซ้อน
- Time Complexity: O(n × m) ด้วย memoization
- Space Complexity: O(n × m)
