กำหนดสตริง s และ pattern p รองรับ wildcard: '?' 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) เริ่มต้น False
- dp[0][0] = True
- เติม dp[0][j] สำหรับ pattern เริ่มต้นด้วย '*'
- เติม 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-1][j] or dp[i][j-1]
ตัวอย่างโค้ด
class Solution(object):
def isMatch(self, s, p):
sl = len(s)
pl = len(p)
dp = [[False for _ in range(pl+1)] for _ 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] = dp[i-1][j] or 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
