正則表達式：
正則表達式（regular expression）就是用一個“字符串”來描述一個特征咧栗，然后去驗證另一個“字符串”是否符合這個特征层宫。比如 表達式“ab+” 描述的特征是“一個 'a' 和 任意個 'b' ”座舍，那么 'ab', 'abb', 'abbbbbbbbbb' 都符合這個特征。
常用的正則表達式符號如下表所示：
正則表達式.png
其中最常用的有如下幾個符號：
“ \ ”: 可以作為轉義字符孤澎，如我們平常編程時的轉義字符類似暇唾，主要時解決匹配特殊字符集，
“\w” : 匹配單詞字符
“ ^ ”: 表示取反剿骨。 如：[^\w] 表示非單詞字符代芜。但是要想匹配'^'符號，我們需要用轉義字符：[^]
"+","?","*": 分別表示匹配前一個字符 大于0次,大于等于0次,0次或1次
“{m}”: 表示匹配前面字符m次
“$”: 表示匹配末尾串
“[\u4e00-\u9fa5]?”： 匹配所有的漢子字符浓利，故[^\u4e00-\u9fa5]?：匹配所有非漢字字符挤庇，用于標點的剔除
其中考察我們編程實現(xiàn)的有四個符號: [. * ? +]。 主要寫出函數(shù)：
boolean isMatch(String a, String p);其中p為模式串贷掖，a為匹配串思路1 ：backtracking:
“*” 表示前面的字符出現(xiàn)>=0 次嫡秕，所以以*之前的點為回溯點。利用遞歸的思路程序如下：
class Solution(object):
cache = {}
def isMatch(self, s, p):
if (s, p) in self.cache:
return self.cache[(s, p)]
if not p:
return not s
if p[-1] == '*':
if self.isMatch(s, p[:-2]):
self.cache[(s, p)] = True
return True
if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
self.cache[(s, p)] = True
return True
if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
self.cache[(s, p)] = True
return True
self.cache[(s, p)] = False
return False
思路2：DP
建立二維dp數(shù)組苹威；其中dp[i+1][j+1] 表示字符s[0.....i]與字符p[0...j]相互匹配昆咽；所以我們關注p[j + 1]的字符是否為‘*’作為我們討論的分類
p[j + 1] != '*': 只需要p[j + 1] == '.' || p[j + 1] == s[i + 1]時 dp[i+1][j = 1] =dp[i][j]
p[j + 1] == '*': 我們需要看前j個是否已經匹配了s[0...i]: 匹配了就讓*為不出現(xiàn)字符。否則看如果p[i] == '.' || p[i] == s[i] 則可以讓其等于一個前方字符
def isMatch(self, s, p):
dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
dp[0][0] = True
for i in range(1, len(p)):
dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
for i in range(len(p)):
for j in range(len(s)):
if p[i] == '*':
dp[i + 1][j + 1] = dp[i - 1][j + 1] or dp[i][j + 1]
if p[i - 1] == s[j] or p[i - 1] == '.':
dp[i + 1][j + 1] |= dp[i + 1][j]
else:
dp[i + 1][j + 1] = dp[i][j] and (p[i] == s[j] or p[i] == '.')
return dp[-1][-1]
