leetcode 248

问题

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.

Example:

1
2
3
Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

分析

思路1: 从low开始采用 {0, 1, 6, 8, 9} 进制压缩的方式来获取下一个待判断的数字直到high。这种做法会超时。

思路2: 通过增加成对数字的方式直接生成对应位数的“中心对称数”，然后再判断是不是在规定的范围内。corner case，奇数时的情况以及第一位不可以是1的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<char>> pairs = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'}};
    int strobogrammaticInRange(string low, string high) {
        int count = 0;
        for (int len = low.size(); len <= high.size(); ++len) {
            string s(len, '0');
            dfs(low, high, s, 0, len-1, count);
        }
        return count;
    }

    void dfs(const string &low, const string &high, string &s, int l, int r, int &count) {
        if (l > r) {
            if ((s.size() == low.size() && s < low) || (s.size() == high.size() && s > high)) {
                return;
            } else {
                count++;
                return;
            }
        } else {
            for (vector<char> &p: pairs) {
                s[l] = p[0];
                s[r] = p[1];
                if ((l == r && p[0] != p[1]) || (s.size() != 1 && s[0]=='0'))
                    continue;
                dfs(low, high, s, l+1, r-1, count);
            }
        }
    }
};