leetcode

10.c (3509B)

---

 #include <stdio.h>
 #include <stdlib.h>
 #include <stdbool.h>
 #include <string.h>
 
 #define DEBUG 0
 #define PDEBUG(...) if (DEBUG) printf(__VA_ARGS__)
 
 #define HTLEN 3000
 
 static bool isMatchInternal(char* s, char* p, int depth) {
 	PDEBUG("isMatch [%s] [%s] depth %d\n", s, p, depth);
 	// fully recursive solution... 
 	// look ahead, how many characters could 
 	int pl = strlen(p);
 	int pn = -1;
 	if (pl > 1) {
 		pn = p[1];
 	}
 
 	if (s[0] == '\0') {
 		// if we're at the end of the pattern 
 		if (p[0] == '\0') {
 			return true;
 		}
 		// OR the next is * then recurse again..
 		if (pn == '*') {
 			return isMatchInternal(s, p+2, depth+1);
 		}
 		// otherwise there is remaining unmatched pattern, so we're not a match
 		return false;
 	} else if (pn == '*') {
 		// how many characters _could_ we match?
 		int n = 0;
 		while ((s[n] == p[0] || p[0] == '.') && s[n] != '\0') {
 			n++;
 		}
 		// try each option
 		for (int i=0; i<=n; i++) {
 			PDEBUG("trying i %d\n", n);
 			if (isMatchInternal(s+i, p+2, depth+1)) {
 				return true;
 			}
 		}
 		return false;
 	} else if (s[0] == p[0] || p[0] == '.') {
 		PDEBUG("s[0] [%c] p[0] [%c] incrementing\n", s[0], p[0]);
 		return isMatchInternal(s+1, p+1, depth+1);
 	} else {
 		return false;
 	}
 }
 
 bool isMatch(char* s, char* p) {
 	return isMatchInternal(s, p, 0);
 }
 
 // bool isMatch(char* s, char* p) {
 // 	PDEBUG("isMatch %s %s\n", s, p);
 // 	int sx = 0, px = 0;
 // 	int pl = strlen(p);
 // 	int sl = strlen(s);
 // 	while (s[sx] != '\0' && p[px] != '\0') {
 // 		int pn = -1;
 // 		if ((px+1) < pl) {
 // 			pn = p[px+1];
 // 		}
 // 		if (pn == '*') {
 // 			PDEBUG("s[sx] %c p[px] %c pn %c\n", s[sx], p[px], pn);
 
 // 			// is this the end of the pattern?
 // 			if ((px+2) == pl) {
 // 				PDEBUG("* at end of string\n");
 // 				// just check all the remaining characters match
 // 				bool res = true;
 // 				for (int i=sx; i<sl; i++) {
 // 					res = res && (s[i] == p[px] || p[px] == '.');
 // 				}
 // 				return res;
 // 			} else {
 // 				// how many characters _could_ we match??
 // 				int sxx = sx;
 // 				while ((s[sxx] == p[px] || p[px] == '.') && s[sxx] != '\0') {
 // 					sxx++;
 // 				}
 // 				// recursively match the remaining trying each possible number of matches. 
 // 				// god this could be slow.
 // 				for (int i=sx; i<(sxx+1); i++) {
 // 					if (isMatch(s+i, p+px+2)) {
 // 						return true;
 // 					}
 // 				}
 // 				return false;
 // 			}
 // 		} else {
 // 			PDEBUG("s[sx] %c p[px] %c\n", s[sx], p[px]);
 // 			if (s[sx] == p[px] || p[px] == '.') {
 // 				sx++;
 // 				px++;
 // 			} else {
 // 				return false;
 // 			}
 // 		}
 // 	}
 // 	// now verify we're at the end of both strings, OR we're at the last character of p and it's a *
 // 	bool res = s[sx] == '\0' && p[px] == '\0';
 // 	PDEBUG("isMatch %s\n", res ? "true": "false");
 // 	return res;
 // }
 
 void test(char* s, char* p, bool exp) {
 	bool act = isMatch(s, p);
 	if (act != exp) {
 		fprintf(stderr, "test s %s p %s failed, exp %s act %s\n", s, p, exp ? "true": "false", act ? "true" : "false");
 	}
 }
 
 int main() {
 	{
 		test("aa", "p", false);
 	}
 	{
 		test("aa", "a*", true);
 	}
 	{
 		test("ab", ".*", true);
 	}
 	{
 		test("aab", "a*", false);
 	}
 	{
 		test("aab", "a*b", true);
 	}
 	{
 		test("aaaaaab", "a*b", true);
 	}
 	{
 		test("aaaaaab", "a*b*", true);
 	}
 	{
 		test("aaaaaabc", "a*b*", false);
 	}
 	{
 		test("aaaaaabc", "a*b*.", true);
 	}	
 	{
 		test("aab", "c*a*b", true);
 	}
 	{
 		test("aaa", "a*a", true);
 	}
 	{
 		test("a", "ab*", true);
 	}
 	{
 		test("abcaaaaaaabaabcabac", ".*ab.a.*a*a*.*b*b*", true);
 	}
 }