No.010：Regular Expression Matching

題目：

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     }

測試代碼地址：

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：如有不正確或提高效率的方法，歡迎留言，謝謝！