回溯

回溯是比较强有力的遍历或枚举算法，掌握这个算法别无他途，只有勤学多练。在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)，用等比公式计算得到2}len(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的正则表达式的实现，其底层看一看是否是回溯的实现，以及正则表达式式怎么降低时间复杂度的。