190121

github16cp · github16cp · commit 8b78f57bf60c · 2019-01-21T15:59:52.000+08:00
diff --git a/剑指Offer/题解.md b/剑指Offer/题解.md
@@ -3775,4 +3775,65 @@ int main() {
 	system("pause");
 	return 0;
 }
-```
+```
+
+# 52. 正则表达式匹配
+请实现一个函数用来匹配包括`.`和`*`的正则表达式。模式中的字符`.`表示任意一个字符，而`*`表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
+
+首先，考虑特殊情况：
+1. 两个字符串都为空，返回true
+2. 当第一个字符串不空（str），而第二个字符串空了(pattern)，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是`a*a*a*a*`,由于`*`之前的元素可以出现0次，所以有可能匹配成功）
+
+之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。
+
+但考虑到pattern下一个字符可能是 `*`， 这里我们分两种情况讨论：
+
+pattern下一个字符为 `*` 或不为 `*`：
+
+1. pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的“匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’,同时str的当前字符不为‘\0’。
+2. pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。这里把这些情况都考虑到：
+
+     * 当`*`匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘*’符号；
+
+     * 当`*`匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况；当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
+
+```C++
+#include<iostream>
+#include<vector>
+using namespace std;
+
+class Solution {
+public:
+	bool match(char* str, char* pattern)
+	{
+		if (*str == '\0' && *pattern == '\0') return true;
+		if(*str != '\0' && *pattern == '\0') return false;
+		if (*(pattern + 1) != '*') {
+			if (*str == *pattern || (*str != '\0' && *pattern == '.')) //匹配任意一个字符
+				return match(str + 1, pattern + 1);
+			else
+				return false;
+		}
+		else {
+			if (*str == *pattern || (*str != '\0' && *pattern == '.'))
+				return match(str, pattern + 2) || match(str + 1, pattern);
+			else 
+				return match(str, pattern + 2);
+		}
+		return false;
+	}
+};
+
+int main() {
+	Solution s;
+	char str1[] = "aaa";
+	char str2[] = "ab*a";
+	cout << s.match(str1, str2) << endl;
+	system("pause");
+	return 0;
+}
+```
+
+# 53. 表示数值的字符串
+
+请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
