กำหนดสตริง s และ pattern p รองรับ regex: '.' match ตัวอักษรเดียว, '*' match 0 หรือมากกว่าของตัวอักษรก่อนหน้า ต้องตรวจสอบว่า s match p หรือไม่
ตัวอย่าง: s="aa", p="a." → True; s="aaaaaa", p="a*" → True
ขั้นตอนการแก้ปัญหา (Dynamic Programming)
- สร้างตาราง dp ขนาด (len(s)+1) x (len(p)+1)
- dp[0][0] = True
- เติม dp[0][j] สำหรับ pattern ที่มี '*' (dp[0][j] = dp[0][j-2] ถ้า p[j-1]=='*')
- เติม dp[i][j]: ถ้า s[i-1]==p[j-1] หรือ p[j-1]=='.' → dp[i][j] = dp[i-1][j-1]; ถ้า p[j-1]=='*' → dp[i][j] = dp[i][j-2] หรือ (ถ้า s[i-1]==p[j-2] หรือ p[j-2]=='.') dp[i][j] = dp[i][j] or dp[i-1][j]
ตัวอย่างโค้ด
class Solution(object):
def isMatch(self, s, p):
ss = len(s)
ps = len(p)
dp = [[False for _ in range(ps+1)] for _ 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] = dp[i][j] or 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
