LeetCode刷题实战248：中心对称数III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
示例
示例:
输入: low = “50”, high = “100”
输出: 3
解释: 69，88 和 96 是三个在该范围内的中心对称数
解题
class Solution {
public:
//使用深度优先构造中心对称数
void dfs(string& low,string& high,int& count,string cur){
if(cur.size()>=low.size()&&cur.size()<=high.size()){//若当前的中心对称数在有效范围之内
//三种当前的中心对称数是无效的情形
//第一种是当前的中心对称数的长度符合要求，但大于最大值
//第二种是当前的中心对称数的长度符合要求，但小于最小值
//第三种是当前的中心对称数的长度大于1，但最高位是0的情形
//若非这三种情形，则说明当前的中心对称数是有效的数，统计数量加1
if(!(cur.size()==high.size()&&cur>high
||cur.size()==low.size()&&cur<low
||cur.size()>=2&&cur[0]=='0')){
++count;
}
}
//若长度越界，则返回
if(cur.size()+2>high.size()){
return;
}
//几种从当前情形生成新的中心对称数的方式
dfs(low,high,count,"0"+cur+"0");
dfs(low,high,count,"1"+cur+"1");
dfs(low,high,count,"6"+cur+"9");
dfs(low,high,count,"9"+cur+"6");
dfs(low,high,count,"8"+cur+"8");
}
int strobogrammaticInRange(string low, string high) {
int count=0;//统计中心对称数的个数
//几种中心对称数的可能的初始情形
dfs(low,high,count,"");
dfs(low,high,count,"1");
dfs(low,high,count,"0");
dfs(low,high,count,"8");
return count;
}
};