Đề bài:
Cho một chuỗi đầu vào (s) và một mẫu (p), thực hiện việc so khớp mẫu đại diện (wildcard) với hỗ trợ cho các ký tự ‘?’ và ‘*’ với các quy tắc sau:
- ‘?’ Khớp với bất kỳ ký tự đơn nào.
- ‘*’ Khớp với bất kỳ chuỗi ký tự nào (bao gồm cả chuỗi rỗng).
Quá trình so khớp phải bao gồm toàn bộ chuỗi đầu vào (không phải là so khớp một phần).
Ví dụ 1:
Input: s = "aa", p = "a" Output: false Giải thích: "a" không khớp với toàn bộ chuỗi "aa".
Ví dụ 2:
Input: s = "aa", p = "*" Output: true Giải thích: '*' khớp với bất kỳ chuỗi ký tự nào.
Ví dụ 3:
Input: s = "cb", p = "?a" Output: false Giải thích: '?' khớp với 'c', nhưng chữ cái thứ hai là 'a', không khớp với 'b'.
Ràng buộc:
- 0 <= độ dài của chuỗi s, p <= 2000
- chuỗi s chỉ chứa các chữ cái tiếng Anh thường.
- chuỗi p chỉ chứa các chữ cái tiếng Anh thường, ký tự ‘?’ hoặc ‘*’.
Giải thích thuật toán bằng C ++
class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length();
const int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;
auto isMatch = [&](int i, int j) -> bool {
return j >= 0 && p[j] == '?' || s[i] == p[j];
};
for (int j = 0; j < p.length(); ++j)
if (p[j] == '*')
dp[0][j + 1] = dp[0][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p[j] == '*') {
const bool matchEmpty = dp[i + 1][j];
const bool matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(i, j)) {
dp[i + 1][j + 1] = dp[i][j];
}
return dp[m][n];
}
};
Đoạn mã trên là một đoạn mã C++ để kiểm tra xem một chuỗi `s` có khớp với một mẫu `p` hay không, sử dụng các ký tự đại diện (wildcard) như ‘?’ và ‘*’. Dưới đây là giải thích về thuật toán trong đoạn mã:
1. Hàm `isMatch` nhận hai chuỗi `s` và `p` là các chuỗi ký tự và trả về giá trị boolean cho biết `s` có khớp với `p` hay không.
2. Đầu tiên, ta khởi tạo hai biến `m` và `n` lần lượt là độ dài của chuỗi `s` và chuỗi `p`.
3. Ta sử dụng một ma trận `dp` có kích thước `(m + 1) × (n + 1)` với các giá trị boolean để lưu trữ các kết quả phù hợp. `dp[i][j]` sẽ mang giá trị `true` nếu chuỗi `s` từ vị trí 0 đến `i-1` khớp với chuỗi `p` từ vị trí 0 đến `j-1`.
4. Ta tạo một hàm lambda `isMatch` nhận hai chỉ số `i` và `j` và kiểm tra xem ký tự tại vị trí `j` trong chuỗi `p` có khớp với ký tự tại vị trí `i` trong chuỗi `s`. Ký tự ‘?’ đại diện cho bất kỳ ký tự đơn nào, nên nếu `p[j]` là ‘?’ hoặc `s[i]` khớp với `p[j]`, hàm sẽ trả về `true`.
5. Tiếp theo, ta thực hiện hai vòng lặp for lồng nhau để đi qua từng phần tử trong chuỗi `p` và `s` và cập nhật giá trị của ma trận `dp`:
– Trong vòng lặp đầu tiên, ta kiểm tra nếu ký tự tại vị trí `j` trong chuỗi `p` là ‘*’, ta gán giá trị của `dp[0][j + 1]` bằng giá trị của `dp[0][j]`. Điều này cho phép ‘*’ khớp với một chuỗi ký tự bất kỳ (bao gồm cả chuỗi rỗng) ở vị trí đầu tiên của chuỗi `s`.
– Trong vòng lặp thứ hai, ta kiểm tra từng phần tử trong chuỗi `s` và `p` và thực hiện các bước sau:
+ Nếu ký tự tại vị trí `j` trong chuỗi `p` là ‘*’, ta kiểm tra hai trường hợp:
- – `matchEmpty` đại diện cho việc chuỗi `s` từ vị trí 0 đến `i-1` khớp với chuỗi `p` từ vị trí 0 đến `j`. Điều này tương đương với giá trị `dp[i+1][j]`.
- – `matchSome` đại diện cho việc chuỗi `s` từ vị trí 0 đến `i` khớp với chuỗi `p` từ vị trí 0 đến `j-1`. Điều này tương đương với giá trị `dp[i][j+1]`.
- – Gán giá trị của `dp[i+1][j+1]` là kết quả của phép logic OR giữa `matchEmpty` và `matchSome`. Điều này sẽ cho phép ‘*’ khớp với một chuỗi ký tự bất kỳ ở vị trí hiện tại trong chuỗi `s`.
+ Ngược lại, nếu ký tự tại vị trí `j` trong chuỗi `p` khớp với ký tự tDưới đây là một giải thích về thuật toán trong đoạn mã:
6. Lớp `Solution` chứa một hàm `isMatch` để kiểm tra xem một chuỗi `s` có khớp với một mẫu `p` hay không.
7. Trong hàm `isMatch`, ta đầu tiên khởi tạo hai biến `m` và `n` là độ dài của chuỗi `s` và chuỗi `p` tương ứng.
8. Tiếp theo, ta tạo một ma trận `dp` có kích thước `(m + 1) × (n + 1)` để lưu trữ các kết quả phù hợp. `dp[i][j]` sẽ mang giá trị `true` nếu chuỗi `s` từ vị trí 0 đến `i-1` khớp với chuỗi `p` từ vị trí 0 đến `j-1`.
9. Ta sử dụng một hàm lambda có tên là `isMatch` để kiểm tra xem hai ký tự tại vị trí `i` và `j` trong chuỗi `s` và `p` có khớp nhau hay không. Ký tự `’?’` khớp với bất kỳ ký tự đơn nào trong chuỗi `s`, còn ký tự `’*’` khớp với bất kỳ chuỗi ký tự nào (bao gồm cả chuỗi rỗng).
10. Trong vòng lặp đầu tiên, ta đi qua từng ký tự trong chuỗi `p` và kiểm tra nếu ký tự đó là `’*’`. Nếu là `’*’`, ta gán giá trị `dp[0][j+1]` bằng giá trị `dp[0][j]`. Điều này đảm bảo rằng `’*’` có thể khớp với một chuỗi ký tự bất kỳ ở vị trí đầu tiên của chuỗi `s`.
11. Tiếp theo, ta sử dụng hai vòng lặp for lồng nhau để đi qua từng phần tử trong chuỗi `s` và chuỗi `p` và cập nhật giá trị của ma trận `dp`.
12. Trong vòng lặp thứ hai, nếu ký tự tại vị trí `j` trong chuỗi `p` là `’?’` hoặc ký tự tại vị trí `i` trong chuỗi `s` khớp với ký tự tại vị trí `j` trong chuỗi `p`, ta gán `dp[i+1][j+1]` bằng giá trị `dp[i][j]`. Điều này cho phép chuỗi `s` từ vị trí 0 đến `i` khớp với chuỗi `p` từ vị trí 0 đến `j`.
13. Trong trường hợp khác, nếu ký tự tại vị trí `j` trong chuỗi `p` là `’*’`, ta cập nhật `dp[i+1][j+1]` bằng giá trị `true` nếu có một trong hai trường hợp sau đúng:
– `dp[i+1][j]` là `true`, tức là chuỗi `s` từ vị trí 0 đến `i` khớp với chuỗi `p` từ vị trí 0 đến `j-1`. Điều này cho phép `’*’` khớp với một chuỗi ký tự bất kỳ ở vị trí hiện tại của chuỗi `s`.
– `dp[i][j+1]` là `true`, tức là chuỗi `s` từ vị trí 0 đến `i-1` khớp với chuỗi `p` từ vị trí 0 đến `j`. Điều này cho phép `’*’` khớp với một chuỗi
Giải thích thuật toán bằng Java
class Solution {
public boolean isMatch(String s, String p) {
final int m = s.length();
final int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*')
dp[0][j + 1] = dp[0][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
final boolean matchEmpty = dp[i + 1][j];
final boolean matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(s, i, p, j)) {
dp[i + 1][j + 1] = dp[i][j];
}
return dp[m][n];
}
private boolean isMatch(final String s, int i, final String p, int j) {
return j >= 0 && p.charAt(j) == '?' || s.charAt(i) == p.charAt(j);
}
}
Giải thích thuật toán bằng Python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
# dp[i][j] := True if s[0..i) matches p[0..j)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
def isMatch(i: int, j: int) -> bool:
return i >= 0 and p[j] == '?' or s[i] == p[j]
for j, c in enumerate(p):
if c == '*':
dp[0][j + 1] = dp[0][j]
for i in range(m):
for j in range(n):
if p[j] == '*':
matchEmpty = dp[i + 1][j]
matchSome = dp[i][j + 1]
dp[i + 1][j + 1] = matchEmpty or matchSome
elif isMatch(i, j):
dp[i + 1][j + 1] = dp[i][j]
return dp[m][n]
0 / 5 - (0 Đánh Giá)