Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input: s = "mississippi", p = "mis*is*p*."
Output: false
Constraints:
0 <= s.length <= 20
0 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
/**
* A Solution by Systematically Trying All Possibilities
*/
typedef struct NodeStruct {
int val;
void *ptr;
struct NodeStruct *next;
}* Node;
typedef struct StackStruct {
int context;
int count;
Node top;
}* Stack;
Stack StackCreateWithContext(int context) {
Stack stk = (Stack)malloc(sizeof(*stk));
stk->count = 0;
stk->context = context;
stk->top = NULL;
return stk;
}
Stack StackCreate() { return StackCreateWithContext(0); }
bool StackIsEmpty(Stack stk) { return stk->count == 0; }
void StackPushVal(Stack stk, int val) {
Node node = (Node)malloc(sizeof(*node));
node->val = val;
node->next = stk->top;
stk->top = node;
stk->count += 1;
}
int StackPopVal(Stack stk) {
int val = stk->top->val;
Node top = stk->top;
stk->top = top->next;
stk->count -= 1;
free(top);
return val;
}
void StackPop(Stack stk) {
Node top = stk->top;
stk->top = top->next;
stk->count -= 1;
void *ptr = top->ptr;
free(top);
}
void StackPush(Stack stk, void *ptr) {
Node top = (Node)malloc(sizeof(*top));
top->ptr = ptr;
top->next = stk->top;
stk->top = top;
stk->count += 1;
}
void* StackTop(Stack stk) { return stk->top->ptr; }
bool check_trailing_repeats(char *p, int j, size_t n) {
if ((n - j) % 2 != 0) return false;
j += 1;
while (j < n) {
if (p[j] != '*') { return false; }
j += 2;
}
return true;
}
bool matchsp(char sc, char pc) { return sc == pc || pc == '.'; }
bool isMatch(char * s, char * p){
if (s == NULL || p == NULL) return false;
size_t m = strlen(s), n = strlen(p);
if (m == 0 && n == 0) return true;
Stack stks = StackCreate();
int i = 0, j = 0;
while (i < m && j < n) {
char sc = s[i], pc = p[j];
bool repeat = j + 1 < n && p[j + 1] == '*';
if (repeat) {
j += 2;
if (matchsp(s[i], pc)) {
Stack stk = StackCreateWithContext(j);
while (i < m && matchsp(s[i], pc)) {
StackPushVal(stk, i);
i++;
}
StackPush(stks, stk);
}
} else {
if (matchsp(sc, pc)) {
i += 1;
j += 1;
} else {
if (!StackIsEmpty(stks)) {
Stack stk = StackTop(stks);
i = StackPopVal(stk);
j = stk->context;
if (StackIsEmpty(stk)) {
StackPop(stks);
free(stk);
}
} else {
return false;
}
}
}
if (i == m) {
if (j == n) {
return true;
} else {
if (check_trailing_repeats(p, j, n)) { return true; }
if (!StackIsEmpty(stks)) {
Stack stk = StackTop(stks);
i = StackPopVal(stk);
j = stk->context;
if (StackIsEmpty(stk)) {
StackPop(stks);
free(stk);
}
}
}
}
}
return i == m && (j == n || check_trailing_repeats(p, j, n));
}
We can further improve this solution by adding dp flags, which managed to bring down the running time from 400+ms to 8ms; here's the code:
typedef struct NodeStruct {
int val;
void *ptr;
struct NodeStruct *next;
}* Node;
typedef struct StackStruct {
int context;
int count;
Node top;
}* Stack;
Stack StackCreateWithContext(int context) {
Stack stk = (Stack)malloc(sizeof(*stk));
stk->count = 0;
stk->context = context;
stk->top = NULL;
return stk;
}
Stack StackCreate() { return StackCreateWithContext(0); }
bool StackIsEmpty(Stack stk) { return stk->count == 0; }
void StackPushVal(Stack stk, int val) {
Node node = (Node)malloc(sizeof(*node));
node->val = val;
node->next = stk->top;
stk->top = node;
stk->count += 1;
}
int StackPopVal(Stack stk) {
int val = stk->top->val;
Node top = stk->top;
stk->top = top->next;
stk->count -= 1;
free(top);
return val;
}
void StackPop(Stack stk) {
Node top = stk->top;
stk->top = top->next;
stk->count -= 1;
void *ptr = top->ptr;
free(top);
}
void StackPush(Stack stk, void *ptr) {
Node top = (Node)malloc(sizeof(*top));
top->ptr = ptr;
top->next = stk->top;
stk->top = top;
stk->count += 1;
}
void* StackTop(Stack stk) { return stk->top->ptr; }
bool check_trailing_repeats(char *p, int j, size_t n) {
if ((n - j) % 2 != 0) return false;
j += 1;
while (j < n) {
if (p[j] != '*') { return false; }
j += 2;
}
return true;
}
bool matchsp(char sc, char pc) { return sc == pc || pc == '.'; }
bool isMatch(char * s, char * p){
if (s == NULL || p == NULL) return false;
size_t m = strlen(s), n = strlen(p);
if (m == 0 && n == 0) return true;
bool **dp = (bool**)malloc(m * sizeof(bool*));
for (int i = 0; i < m; i++) {
dp[i] = (bool*)malloc(n * sizeof(bool));
for (int j = 0; j < n; j++) { dp[i][j] = false; }
}
Stack stks = StackCreate();
int i = 0, j = 0;
while (i < m && j < n) {
bool backtrack = false;
if (!dp[i][j]) {
dp[i][j] = true;
char sc = s[i], pc = p[j];
bool repeat = j + 1 < n && p[j + 1] == '*';
if (repeat) {
j += 2;
if (matchsp(s[i], pc)) {
Stack stk = StackCreateWithContext(j);
while (i < m && matchsp(s[i], pc)) {
StackPushVal(stk, i);
i++;
}
StackPush(stks, stk);
}
} else {
if (matchsp(sc, pc)) {
i += 1;
j += 1;
} else {
if (!StackIsEmpty(stks)) {
backtrack = true;
} else {
return false;
}
}
}
if (i == m) {
if (j == n) {
return true;
} else {
if (check_trailing_repeats(p, j, n)) { return true; }
if (!StackIsEmpty(stks)) { backtrack = true; }
}
}
}
if (backtrack || (i < m && j < n && dp[i][j])) {
Stack stk = StackTop(stks);
i = StackPopVal(stk);
j = stk->context;
if (StackIsEmpty(stk)) {
StackPop(stks);
free(stk);
}
}
}
return i == m && (j == n || check_trailing_repeats(p, j, n));
}
网友评论