回溯
回溯是比较强有力的遍历或枚举算法，掌握这个算法别无他途，只有勤学多练。在leetcode中的第10题就是一个比较有意思题目，一个正则表达式的实现，题目是这样的
#'.' Matches any single character.
#'*' Matches zero or more of the preceding element.
#The matching should cover the entire input string (not partial).
#Note:
#s could be empty and contains only lowercase letters a-z.
#p could be empty and contains only lowercase letters a-z, and characters like . or *.
实现
对于正则表达式，大家应该比较熟悉，这个题目就是实现正则表达式中的.和*。我们最简单的做法就是使用正则表达式，其缺点后续再说明。
对于比对中文本的位置和正则表达式的位置分别用textPos和patternPos来表示，对于'.'的语义就是说，如果比对位是'.'，那么就讲两个位置都加1。如果textPos位置的字符和patternPos的字符相同，那么两个位置加1。
接着就是难点的表达，这里按照语义，需要表达的就是0和多个，对于0，例如说“a”和"b"，为了表达0，那么textPos不变，讲patternPos+2；如果表达多个，例如"aaaa"和"a*”，将textPos加1即可，因为我们基于回溯去考虑问题，不论这里有几个a，只需要考虑加1,下个字符基于这次的结果继续考虑。因为考虑的是0和多个，这里0和多个之间就是或的关系，可能一个都没有，可能有多个。
再回去看一下回溯的模版
def backtracking(level, paras):
if exist_condition(level):
return
state = keepsate(level) #保存当前状态
backtracking(level+1, paras):
reverseState(level, state) #恢复当前状态
我们的代码如下：
def isMatch(self, text, pattern):
if not pattern or not text: return False
self.textLen, self.patternLen = len(text), len(pattern)
self.text, self.pattern, self.matched = text, pattern, False
self.match(0, 0)
return self.matched
def match(self, textPos, patternPos):
if self.matched: return 退出条件
if patternPos == self.patternLen:
self.matched = textPos == self.textLen
return #退出条件
first_match = textPos < self.textLen and self.pattern[patternPos] in {self.text[textPos], '.'} #字符匹配或者是.匹配
if self.patternLen - patternPos >= 2 and self.pattern[patternPos+1] == '*':
return first_match and self.match(textPos + 1, patternPos) or self.match(textPos, patternPos + 2) # *的0和多个的逻辑，这里是或者的关系
else:
return first_match and self.match(textPos + 1, patternPos + 1) #text和pattern位置+1处理。
比对模版，首先是退出条件，回溯必须有退出条件，然后是对于的语义表达和非的语义表达。我们基于语义来思考问题，从而避免了陷入递归中。
如下是C语言版的实现，看起来更加清爽：
bool isMatch(char* s, char* p) {
int sLen = strLen(s);
int sPat = strLen(p);
if (0 == sPat) {
return 0 == sLen;
}
bool firstMatch = 0 != sLen && (p[0] == '.' || p[0] == s[0]);
if ((sPat > 1) && (p[1] == '*')) {
return firstMatch && isMatch(s + 1, p) || isMatch(s, p + 2);
} else {
return firstMatch && isMatch(s + 1, p + 1);
}
}
缺点
如上，特别是对于的语义表达式个or的关系，如果用递归树展开，可以看到这是一个非常复杂的递归树,例如说aa和a
----------（aa a)
-----(a a)----------(aa "")
("" a*) -- (a "")
高度是len(text)，每一列最大是2^(len(text)-1)个元素，这样计算为
1 + 2 + 2^2 + ... + 2(len(text)-1)，用等比公式计算得到2len(text) -1，时间复杂度为O(2^len(text)，这是一个指数级的复杂度。因此需要进行优化，怎么优化，可以使用动态规划的思路进行优化。
如下动态规划的实现，也很清爽：
def isMatch(self, text, pattern):
dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
dp[-1][-1] = True
for i in range(len(text), -1, -1):
for j in range(len(pattern) - 1, -1, -1):
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j + 1 < len(pattern) and pattern[j + 1] == '*':
d[i][j] = first_match and d[i + 1][j] or d[i][j + 2]
else:
d[i][j] = first_match and d[i + 1][j + 1]
return dp[0][0]
和上面思路是一样的，用一张表将匹配结果储存起来。时间复杂度为O(len(text)*len(pattern)，这个复杂度就远小于上面使用回溯的指数级的实际复杂度了。
小结
这个例子是个非常有意思的例子，通过回溯，我们能比较容易的写出枚举型的实现，但是发现复杂度是指数型的，因此考虑用动态规划来实现，可以达到低一个数量级的实际复杂度。
学习完了，我们可以看一下java的正则表达式的实现，其底层看一看是否是回溯的实现，以及正则表达式式怎么降低时间复杂度的。
