Đề bài:
Cho một chuỗi đầu vào s và một mẫu p, triển khai việc so khớp biểu thức chính quy với hỗ trợ cho ‘.’ và ‘*’ trong đó:
- ‘.’ khớp với bất kỳ ký tự đơn nào.
- ‘*’ khớp với không hoặc nhiều hơn một phần tử trước đó.
Quá trình so khớp này phải bao phủ toàn bộ chuỗi đầu vào (không phải là 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 = "a*" Output: true Giải thích: '*' có nghĩa là không hoặc nhiều hơn một phần tử trước đó, trong trường hợp này là 'a'. Do đó, bằng cách lặp lại 'a' một lần, nó trở thành "aa".
Ví dụ 3:
Input: s = "ab", p = ".*" Output: true Giải thích: ".*" có nghĩa là "không hoặc nhiều hơn (*) của bất kỳ ký tự nào (.)".
Ràng buộc:
- 1 <= độ dài của s <= 20
- 1 <= độ dài của p <= 20
- s chỉ chứa các chữ cái tiếng Anh thường.
- p chỉ chứa các chữ cái tiếng Anh thường, dấu chấm (.), và ký tự sao (*).
- Đảm bảo rằng cho mỗi ký tự sao (*) xuất hiện, sẽ có một ký tự hợp lệ trước đó để khớp.
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 + 1] = true;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p[j] == '*') {
// The minimum index of '*' is 1.
const bool noRepeat = dp[i + 1][j - 1];
const bool doRepeat = isMatch(i, j - 1) && dp[i][j + 1];
dp[i + 1][j + 1] = noRepeat || doRepeat;
} else if (isMatch(i, j)) {
dp[i + 1][j + 1] = dp[i][j];
}
return dp[m][n];
}
};
Đoạn mã trên triển khai thuật toán đệ quy động (dynamic programming) để giải quyết bài toán so khớp chuỗi (string matching) với mẫu (pattern) chứa các ký tự đặc biệt như ‘.’ và ‘*’.
Thuật toán này sử dụng một ma trận `dp` có kích thước `(m+1) x (n+1)`, trong đó `m` là độ dài của chuỗi `s` và `n` là độ dài của chuỗi `p`. Giá trị `dp[i][j]` trong ma trận `dp` sẽ là `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`, và là `false` trong trường hợp ngược lại.
Để tính toán giá trị của `dp[i][j]`, thuật toán sử dụng hai vòng lặp `for` lồng nhau. Trong đó, vòng lặp bên ngoài duyệt qua từng ký tự của chuỗi `s` (từ 0 đến `m-1`), và vòng lặp bên trong duyệt qua từng ký tự của chuỗi `p` (từ 0 đến `n-1`).
Trong mỗi vòng lặp, thuật toán kiểm tra các trường hợp sau đây:
1. Nếu ký tự hiện tại của `p` là ‘*’, ta phải xử lý hai trường hợp con:
– Trường hợp 1 (`noRepeat`): Nếu bỏ qua ký tự ‘*’ và ký tự trước đó của `p` (tức là `p[j-1]`), chuỗi `s` từ vị trí 0 đến `i-1` vẫn khớp với chuỗi `p` từ vị trí 0 đến `j-2`. Tức là, `dp[i+1][j+1] = dp[i+1][j-1]`.
– Trường hợp 2 (`doRepeat`): Nếu ký tự trước đó của `p` (tức là `p[j-1]`) khớp với ký tự hiện tại của `s` (tức là `s[i]`), và chuỗi `s` từ vị trí 0 đến `i-1` khớp với chuỗi `p` từ vị trí 0 đến `j`. Tức là, `dp[i+1][j+1] = dp[i][j+1]`.
Khi đó, giá trị của `dp[i+1][j+1]` là kết hợp của hai trường hợp trên: `dp[i+1][j+1] = noRepeat || doRepeat`.
2. Nếu ký tự hiện tại của `p` không phải là ‘*’ và ký tự hiện tại của `p` khớp với ký tự hiện tại của `s`, tức là `s[i]` khớp với `p[j]`, ta có thể tiếp tục so khớp các ký tự tiếp theo của `s` và `p`. Do đó, `dp[i+1][j+1] = dp[i][j]`.
Cuối cùng, sau khi thực hiện toàn bộ vòng lặp, giá trị của `dp[m][n]` sẽ là kết quả của bài toán, tức là chuỗi `s` có khớp với chuỗi `p` hay không.
Đoạn mã cũng sử dụng một hàm lambda `isMatch` để kiểm tra xem ký tự `s[i]` có khớp với ký tự `p[j]` hay không. Nếu `p[j]` là ký tự ‘.’ hoặc `s[i]` khớp với `p[j]`, hàm `isMatch` sẽ trả về `true`, ngừng lại đó là `false`.
Trong quá trình khởi tạo ma trận `dp`, giá trị `dp[0][0]` được đặt là `true` để tương ứng với trường hợp cả hai chuỗi `s` và `p` đều rỗng.
Sau đó, vòng lặp đầu tiên kiểm tra các trường hợp đặc biệt khi ký tự `’*’` xuất hiện ở vị trí đầu tiên của `p`. Nếu `p[j]` là `’*’` và `dp[0][j-1]` (tức là chuỗi `p` từ vị trí 0 đến `j-2`) đã khớp với chuỗi rỗng `s`, ta có thể coi `’*’` như một ký tự rỗng (không xuất hiện) và chuỗi `p` từ vị trí 0 đến `j-1` vẫn khớp với chuỗi rỗng `s`. Khi đó, ta đặt `dp[0][j+1]` là `true`.
Cuối cùng, sau khi hoàn thành vòng lặp, giá trị `dp[m][n]` sẽ là kết quả của bài toán, cho biết chuỗi `s` có khớp với chuỗi `p` hay không.
Đây là một triển khai của thuật toán đệ quy động để giải quyết bài toán so khớp chuỗi, được áp dụng trong một lớp `Solution` của C++.
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 + 1] = true;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
// The minimum index of '*' is 1.
final boolean noRepeat = dp[i + 1][j - 1];
final boolean doRepeat = isMatch(s, i, p, j - 1) && dp[i][j + 1];
dp[i + 1][j + 1] = noRepeat || doRepeat;
} 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 j >= 0 and p[j] == '.' or s[i] == p[j]
for j, c in enumerate(p):
if c == '*' and dp[0][j - 1]:
dp[0][j + 1] = True
for i in range(m):
for j in range(n):
if p[j] == '*':
# The minimum index of '*' is 1.
noRepeat = dp[i + 1][j - 1]
doRepeat = isMatch(i, j - 1) and dp[i][j + 1]
dp[i + 1][j + 1] = noRepeat or doRepeat
elif isMatch(i, j):
dp[i + 1][j + 1] = dp[i][j]
return dp[m][n]
0 / 5 - (0 Đánh Giá)