Strobogrammatic Number II

这个题其实很有点类似于DP里面的区间型，首先最后结果的长度要不是偶数要不是奇数，而他们唯一的区别就是中心是围绕一个词对称还是围绕一个空挡对称，现在不考虑对称中心，其他地方的词明显可以看出是对称的，只是这种对称不是传统的那种对称，而是这里说的strobogrammatic对称，也就是说当一个位置出现6时，它围绕中心对称的位置应该是9，也就是我们这里存储的哈希表里面的k-v关系，接下来只需要用回溯去完成就可以了

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        mirror = {'1':'1', '0':'0', '6':'9', '9':'6', '8':'8'}
        result = []
        self.helper(1, n, result, mirror, '')
        return result

    def helper(self, start, end, res, mirror, tmp):
        if start > end:
            res.append(tmp[:])
            return 

        if start == end:
            for num, mirNum in mirror.items():
                if num == mirNum:
                    self.helper(start + 1, end - 1, res, mirror, 
                                tmp[:len(tmp) / 2] + num + \
                                tmp[len(tmp) / 2:])
        else:
            for num, mirNum in mirror.items():
                if start != 1 or num != '0':
                    self.helper(start + 1, end - 1, res, mirror,
                            tmp[:len(tmp) / 2] + num + \
                            mirNum + tmp[len(tmp) / 2:])

Discussion里面的纯递归方法很简洁，但是个人觉得自己这种回溯的方法比较容易理解一些