Cho chuỗi s và pattern p. Hỗ trợ ký tự đại diện: '?' khớp 1 ký tự bất kỳ, '*' khớp 0 hoặc nhiều ký tự. Ví dụ: s="aa", p="a?" -> true; s="aaaaaa", p="a*" -> true.
Các bước giải quyết (Dynamic Programming):
- dp[i][j] = true nếu s[:i] khớp p[:j]
- Khởi tạo dp[0][0] = true
- Xử lý '*' ở đầu pattern: dp[0][i] = dp[0][i-1] nếu p[i]=='*'
- Điền bảng: nếu s[i]==p[j] hoặc p[j]=='?' -> dp[i][j]=dp[i-1][j-1]; nếu p[j]=='*' -> dp[i][j]=dp[i-1][j] or dp[i][j-1]
Ví dụ
class Solution(object):
def isMatch(self, s, p):
sl = len(s)
pl = len(p)
dp = [[False for i in range(pl+1)] for j 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] = max(dp[i-1][j], dp[i][j-1])
return dp[sl][pl]
ob = Solution()
print(ob.isMatch("aa", "a?"))
print(ob.isMatch("aaaaaa", "a*"))
Đầu vào
"aa", "a?" "aaaaaa", "a*"
Đầu ra
True True