Giả sử chúng ta có một chuỗi đầu vào s và một chuỗi đầu vào khác p. Đây là chuỗi chính và p là mẫu. Chúng ta phải xác định một phương thức có thể khớp với mẫu trong chuỗi. Vì vậy, chúng tôi phải triển khai điều này cho một biểu thức chính quy, hỗ trợ các ký tự đại diện như ‘?’ Và ‘*’.
-
Dấu chấm ‘?’ Khớp với bất kỳ ký tự đơn nào
-
Dấu sao ‘*’ khớp với 0 hoặc nhiều ký tự.
Vì vậy, ví dụ:nếu đầu vào là s =“aa” và p =“a?”, Thì nó sẽ là đúng, đối với cùng một chuỗi đầu vào, nếu mẫu là “? *”, Thì nó sẽ là đúng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ss:=kích thước của s và ps:=kích thước của p
-
tạo dp thành ma trận có kích thước ss x ps và điền vào giá trị này bằng giá trị false
-
Cập nhật p và s bằng cách thêm một khoảng trống trước các dấu này
-
Đối với tôi trong phạm vi từ 1 đến ps -
-
nếu p [i] =sao, thì
-
dp [0, i]:=dp [0, i - 1]
-
-
-
cho tôi trong phạm vi từ 1 đến ss
-
cho j trong phạm vi 1 đến ps
-
nếu s [i] là p [j] hoặc p [j] là ‘?’ thì
-
dp [i, j]:=dp [i - 1, j - 1]
-
-
ngược lại khi p [j] là dấu sao thì
-
dp [i, j]:=max của dp [i - 1, j] và dp [i, j - 1]
-
-
-
-
trả về dp [ss, ps]
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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