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 s 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 các 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ợ ‘.’ Và ‘*’.
-
Dấu chấm ‘.’ Đối sánh với bất kỳ ký tự đơn nào
-
Dấu sao ‘*’ đối sánh với không hoặc nhiều phần tử trước đó.
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 2 đến ps -
-
dp [0, i]:=dp [0, i - 2] khi p [i] là dấu sao, ngược lại Sai
-
-
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à dấu chấm, thì
-
dp [i, j]:=dp [i - 1, j - 1]
-
-
ngược lại khi p [j] là dấu sao thì
-
dp [i, j]:=dp [i, j - 2]
-
nếu s [i] là p [j - 1] hoặc p [j - 1] là dấu chấm, thì
-
dp [i, j]:=max của dp [i, j] và dp [i - 1, j]
-
-
-
-
-
trả về dp [ss, ps]
Ví dụ
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):
ss = len(s)
ps = len(p)
dp = [[False for i in range(ps+1)] for j 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] = max(dp[i][j],dp[i-1][j])
return dp[ss][ps]
ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*")) Đầu vào
"aa", "a." "aaaaaa", "a*"
Đầu ra
True True