No.010：Regular Expression Matching，no.010matching
題目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Some Examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("aab", ".*a") → false
isMatch("aab", ".*ab") → true
官方難度：
Hard
翻譯：
實現字符串正則表達式匹配，支持特殊符號"."和"*"。
"."可以匹配任意單個字符。
"*"可以匹配0個或更多的在*之前的字符。
匹配算法應該能夠匹配以下所有的例子，而非部分。
例子：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("aab", ".*a") → false
isMatch("aab", ".*ab") → true
思路：
1.只考慮正則表達式的匹配字符串只包括"*"和"."兩種特殊符號，其余特殊符號（包括括號）不在考慮范圍之內。
2.以待解析的字符串長度為基准，開始遍歷。
3.如果遍歷途中，出現待解析字符串尚存，而正則字符串不在了，或反之的情況，返回失敗。
4.從第一個字符開始，不考慮特殊符號的情況下，若匹配，進行待解析和正則字符串的下一個匹配工作。
5.特殊字符串"."單獨出現的情況，當次匹配直接通過。
6.特殊字符串"*"單獨出現的情況，計算"*"上一個字符在待解析字符串中的長度，待解析字符串在下次計算中會跳過那個長度（包括0的情況）。
7.特殊字符串".*"組合出現的情況，這種情況可以匹配，任意長，任意內容的字符串。如".*"可以匹配"abhsjksdhak"，".*a"可以匹配"dhaudhjoaidhaida"但是不能匹配"bdab"。
8.出現7的情況，需要考慮，遍歷待解析字符串剩余部分，能否匹配正則字符串".*"之後的部分。如"ab.*c.d"和"abctucid"，需要依次檢查"ctucid"是否匹配"c.d"，"tucid"是否匹配"c.d"，直至"d"是否匹配"c.d"，只要存在一次匹配成功，就返回true。
解題中可能遇到的困難：
1.注意待解析字符串遍歷完畢之後，需要對正則字符串的長度做檢驗。
2.".*"的處理的方法，是和任意字符+"*"的方法寫在一起的，返回值是一個長度，注意處理結束返回一個特殊值，不要影響其他操作。
解題代碼：
![]()
1 private static boolean method(String str, String regularStr) {
2 String strWithoutHead = str;
3 String regularStrWithoutHead = regularStr;
4 int alreadyMatchedLength = 0;
5 // 待處理的正則字符串
6 String regularStrToDeal = null;
7 int strLengthToReduce;
8 while (alreadyMatchedLength < str.length()) {
9 // 因為退出條件是解析完成字符串長度=原長度，
10 // 所以一次循環完成時，要判斷一下，正則的長度夠不夠
11 if (regularStrWithoutHead.length() == 0) {
12 return false;
13 }
14 if (regularStrWithoutHead.length() > 1 && regularStrWithoutHead.substring(1, 2).equals("*")) {
15 // 第二個數是"*"情況
16 regularStrToDeal = regularStrWithoutHead.substring(0, 2);
17 // 考慮到".*"的情況，把剩余整個正則和待處理字符串傳進去
18 strLengthToReduce = matchStarLength(strWithoutHead, regularStrWithoutHead);
19 // ".*"的特殊處理，因為有遞歸，這裡就是一個出口
20 if (strLengthToReduce == -1) {
21 return true;
22 } else if (strLengthToReduce == -2) {
23 return false;
24 }
25 } else {
26 // 單個匹配情況
27 regularStrToDeal = regularStrWithoutHead.substring(0, 1);
28 if (!singleStringMatch(strWithoutHead.substring(0, 1), regularStrToDeal)) {
29 return false;
30 }
31 strLengthToReduce = 1;
32 }
33 // 增加已處理的字符串長度
34 alreadyMatchedLength += strLengthToReduce;
35 // 去頭
36 strWithoutHead = str.substring(alreadyMatchedLength);
37 regularStrWithoutHead = regularStrWithoutHead.substring(regularStrToDeal.length());
38 }
39 // 待解析完成，但正則還有
40 if (regularStrWithoutHead.length() > 0) {
41 return false;
42 }
43 return true;
44 }
45
46 // 單個字符匹配問題
47 private static boolean singleStringMatch(String str, String regularStr) {
48 // 特殊符號"."處理
49 if (regularStr.equals(".")) {
50 return true;
51 } else if (str.equals(regularStr)) {
52 return true;
53 }
54 return false;
55 }
56
57 // 由於"*"一定會匹配成功，返回原字符串的匹配長度
58 // str不是原字符串，是"*"開始匹配的第一個位置
59 private static int matchStarLength(String str, String regularString) {
60 int length = 0;
61 if (regularString.substring(0, 1).equals(".")) {
62 // 最最最煩的一點：".*"處理
63 // 先把對應的正則字符串去掉".*"
64 String regularRemain = regularString.substring(2);
65 // ".*"之後不跟，匹配一切
66 if (regularRemain.equals("")) {
67 // 返回剩下的字符串長度
68 return str.length();
69 }
70 // 用余下的東西遞歸
71 for (int i = 0; i < str.length(); i++) {
72 String remain = str.substring(i);
73 // 開始遞歸
74 if (method(remain, regularRemain)) {
75 // 只要出現true，直接整個都可以匹配
76 return -1;
77 }
78 }
79 // 余下的都不成功，表示整個不匹配
80 return -2;
81 } else {
82 // 正常字符+"*"
83 String regularInUse = regularString.substring(0, 1);
84 for (int i = 0; i < str.length(); i++) {
85 if (regularInUse.equals(str.substring(i, i + 1))) {
86 length++;
87 } else {
88 break;
89 }
90 }
91 }
92 return length;
93 }
View Code
測試代碼地址：
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/hard/Q010.java
LeetCode題目地址：
https://leetcode.com/problems/regular-expression-matching/
PS：寫完才發現，不使用循環待解析字符串，直接對剩余的字符串使用遞歸，可能是一種更好的思想。
PPS：如有不正確或提高效率的方法，歡迎留言，謝謝！
