248. Strobogrammatic Number III

对称数和回文很像，符合的定义也是从中间往两遍拓。要求返回所有的数目，DFS或DP。参考了grandsong的题目和解法，依次根据不同的可能长度发起遍历，当遍历到符合长度时检查首字母是否为0，和low长度相同时值是否小于low的值以及和high长度相同时值是否大于high的值。感觉还可以再优化，但没看到有人写出DP递推式。

class Solution {
public:
    void dfs(string low, string high, string path, int len, int &res) {
        if (path.size() == len) {
            if (!(len != 1 && path[0] == '0') && 
                !(len == low.size() && path.compare(low) < 0) && 
                    !(len == high.size() && path.compare(high) > 0)) {
                ++res;
            }
            return;
        }
        dfs(low, high, "0" + path + "0", len, res);
        dfs(low, high, "1" + path + "1", len, res);
        dfs(low, high, "6" + path + "9", len, res);
        dfs(low, high, "8" + path + "8", len, res);
        dfs(low, high, "9" + path + "6", len, res);
    }

    int strobogrammaticInRange(string low, string high) {
        int res = 0;
        for (int i = low.size(); i <= high.size(); ++i) {
            dfs(low, high, "", i, res);
            dfs(low, high, "0", i, res);
            dfs(low, high, "1", i, res);
            dfs(low, high, "8", i, res);
        }
        return res;
    }    
}