leetcode/0010-RegularExpressionMatching.cpp at master · Yellow-Pay/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define DEBUG

class Solution {
public:
	bool isMatch(string s, string p) {
		unsigned s_size = s.size();
		unsigned p_size = p.size();
		vector<vector<bool>> table;
		vector<bool> row;
		row.resize(s_size + 1, false);
		table.resize(p_size + 1, row);
		table[p_size][s_size] = true;
		for (int i = p_size - 1; i >= 0; --i) {
			for (int j = s_size - 1; j >= 0; --j) {
				if (s[j] == p[i] || p[i] == '.') {
					table[i][j] = table[i][j] | table[i+1][j+1];
				} else if (p[i] == '*') {
					char prefix = p[i - 1];
					bool any = (prefix == '.');
					if (any) {
						for (int k = j; k <= s_size; k++) {
							if (table[i + 1][k]) {
								table[i][j] = true;
								break;
							}
						}
					} else {
						for (int k = j; k <= s_size; k++) {
							if (table[i + 1][k]) {
								table[i][j] = true;
								break;
							}
							if (s[k] != prefix) {
								break;
							}
						}
					}
					for (int k = 0; k <= s_size; k++) {
						if (table[i+1][k]) {
							table[i][k] = true;
							table[i - 1][k] = true;
						}
					}
				}
				if (i + 1 < p_size && p[i+1] == '*') {
					table[i][j] = table[i][j] | table[i+1][j];
				}
			}
			if (p[i] == '*') {
				for (int k = 0; k <= s_size; k++) {
					if (table[i+1][k]) {
						table[i][k] = true;
						table[i - 1][k] = true;
					}
				}
			}
		}
#ifdef DEBUG
		cout << ' ' << ' ';
		for (int j = 0; j < s_size; j++) {
			cout << s[j] << ' ';
		}
		cout << endl;
		for (int i = 0; i <= p_size; i++) {
			if (i != p_size) cout << p[i] << " ";
			if (i == p_size) cout << ' ' << ' ';
			for (int j = 0; j <= s_size; j++) {
				cout << table[i][j] << " ";
			}
			cout << endl;
		}
#endif
		return table[0][0];
	};
};

struct testcase {
	string s;
	string p;
};

#define TESTCASES 6

struct testcase testcases[TESTCASES] = {
	{"", ".*"},
	{"mississippi", "mis*is*p*."},
	{"aa", "a*"},
	{"aaa", ".*"},
	{"aab", "c*a*b"},
	{"a", "ab*"},
};

int main() {
	Solution sol;
	for (int i = 0; i < TESTCASES; i++) {
		string s = testcases[i].s;
		string p = testcases[i].p;
		cout << "string = " << s << " pattern = " << p << endl;
		if (sol.isMatch(s, p)) {
			cout << "Match!" << endl;
		} else {
			cout << "Not match!" << endl;
		}
		cout << endl;
	}
	return 0;
}