中心对称数 III

本题使用DFS+记忆化搜索的方法来统计在给定范围内的中心对称数的个数。主要思路是：从高位到低位依次构造中心对称数，在构造的过程中，根据已经构造的前缀判断剩余部分是否能够构成中心对称数，如果可以直接计算出个数，避免重复搜索。同时使用记忆化存储已经搜索过的状态，降低时间复杂度。

时间复杂度: O(n * 5^(n/2))

空间复杂度: O(n * 5^(n/2))

```python
class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        def count(num: str):
            def flip(s):
                match = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}  # 定义翻转映射
                ans  = ""
                for ch in s:
                    ans += match[ch]
                return ans

            @cache
            def dfs(pos: int, path: str, limit: bool, start: int) -> int:
                digits = [0,1,6,8,9]  # 可选的数字
                if pos == len(num):  # 已经构造完整个数字
                    return int(start >= 0 and path in {"0","1","8"})  # 判断构造的数是否为中心对称数
                ans  = 0
                if start >= 0:  # 已经开始构造中心对称数
                    if 2 * (pos-start) >= len(num)-start:  # 已经构造了一半以上的数字
                        if not limit:  # 没有上界限制
                            if (len(num)-start) % 2 == 1:  # 数字长度为奇数
                                return int(path in {"0","1","8"})  # 判断当前构造的数是否为中心对称数
                            else:  # 数字长度为偶数
                                return 1  # 只有一种可能
                        else:  # 有上界限制
                            s = path
                            if len(num) % 2 == 0:  # 数字长度为偶数
                                s = s + flip(path[len(path)-1::-1])  # 补全右半部分
                            else:  # 数字长度为奇数
                                s = s + flip(path[len(path)-2::-1])  # 补全右半部分
                            return int(s <= num)  # 判断构造的数是否在范围内
                    else:  # 还未构造一半的数字
                        for d in digits:
                            if limit and d > int(num[pos]):  # 超出上界限制，停止搜索
                                break
                            newLimit = limit and d == int(num[pos])  # 更新上界限制条件
                            if newLimit:  # 当前位取到上界
                                ans += dfs(pos+1, path+str(d),True, start)
                            else:  # 当前位未取到上界
                                ans += dfs(pos+1, str(d), False, start)
                else:  # 还未开始构造中心对称数
                    ans += dfs(pos+1, "", False, -1)  # 跳过当前位
                    for d in digits:
                        if d == 0:  # 不能以0开头
                            continue
                        if limit and d > int(num[pos]):  # 超出上界限制，停止搜索
                            break
                        newLimit = limit and d == int(num[pos])  # 更新上界限制条件
                        if newLimit:  # 当前位取到上界
                            ans += dfs(pos+1, path+str(d), True, pos)
                        else:  # 当前位未取到上界
                            ans += dfs(pos+1, str(d), False, pos)
                return ans
            return dfs(0, "", True, -1) + 1
        ans  = count(high) - count(low)  # 计算范围内的中心对称数个数
        match = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
        for i in range((len(low)+1)//2):
            if low[i] not in match or low[len(low)-1-i] != match[low[i]]:
                break
        else:
            ans += 1  # 如果下界本身是中心对称数，需要加1
        return ans
```