Skip to content

248. Strobogrammatic Number III πŸ”’

Description

Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high].

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

 

Example 1:

Input: low = "50", high = "100"
Output: 3

Example 2:

Input: low = "0", high = "0"
Output: 1

 

Constraints:

  • 1 <= low.length, high.length <= 15
  • low and high consist of only digits.
  • low <= high
  • low and high do not contain any leading zeros except for zero itself.

Solutions

Solution 1: Recursion

If the length is \(1\), then the strobogrammatic numbers are only \(0, 1, 8\); if the length is \(2\), then the strobogrammatic numbers are only \(11, 69, 88, 96\).

We design a recursive function \(dfs(u)\), which returns the strobogrammatic numbers of length \(u\).

If \(u\) is \(0\), return a list containing an empty string, i.e., [""]; if \(u\) is \(1\), return the list ["0", "1", "8"].

If \(u\) is greater than \(1\), we traverse all the strobogrammatic numbers of length \(u - 2\). For each strobogrammatic number \(v\), we add \(1, 8, 6, 9\) to both sides of it, and we can get the strobogrammatic numbers of length \(u\).

Note that if \(u \neq n\), we can also add \(0\) to both sides of the strobogrammatic number.

Let the lengths of \(low\) and \(high\) be \(a\) and \(b\) respectively.

Next, we traverse all lengths in the range \([a,..b]\). For each length \(n\), we get all strobogrammatic numbers \(dfs(n)\), and then check whether they are in the range \([low, high]\). If they are, we increment the answer.

The time complexity is \(O(2^{n+2} \times \log n)\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        def dfs(u):
            if u == 0:
                return ['']
            if u == 1:
                return ['0', '1', '8']
            ans = []
            for v in dfs(u - 2):
                for l, r in ('11', '88', '69', '96'):
                    ans.append(l + v + r)
                if u != n:
                    ans.append('0' + v + '0')
            return ans

        a, b = len(low), len(high)
        low, high = int(low), int(high)
        ans = 0
        for n in range(a, b + 1):
            for s in dfs(n):
                if low <= int(s) <= high:
                    ans += 1
        return ans

 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
32
33
34
35
36
37
38
class Solution {
    private static final int[][] PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
    private int n;

    public int strobogrammaticInRange(String low, String high) {
        int a = low.length(), b = high.length();
        long l = Long.parseLong(low), r = Long.parseLong(high);
        int ans = 0;
        for (n = a; n <= b; ++n) {
            for (String s : dfs(n)) {
                long v = Long.parseLong(s);
                if (l <= v && v <= r) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private List<String> dfs(int u) {
        if (u == 0) {
            return Collections.singletonList("");
        }
        if (u == 1) {
            return Arrays.asList("0", "1", "8");
        }
        List<String> ans = new ArrayList<>();
        for (String v : dfs(u - 2)) {
            for (var p : PAIRS) {
                ans.add(p[0] + v + p[1]);
            }
            if (u != n) {
                ans.add(0 + v + 0);
            }
        }
        return ans;
    }
}

 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
32
33
using ll = long long;

class Solution {
public:
    const vector<pair<char, char>> pairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};

    int strobogrammaticInRange(string low, string high) {
        int n;
        function<vector<string>(int)> dfs = [&](int u) {
            if (u == 0) return vector<string>{""};
            if (u == 1) return vector<string>{"0", "1", "8"};
            vector<string> ans;
            for (auto& v : dfs(u - 2)) {
                for (auto& [l, r] : pairs) ans.push_back(l + v + r);
                if (u != n) ans.push_back('0' + v + '0');
            }
            return ans;
        };

        int a = low.size(), b = high.size();
        int ans = 0;
        ll l = stoll(low), r = stoll(high);
        for (n = a; n <= b; ++n) {
            for (auto& s : dfs(n)) {
                ll v = stoll(s);
                if (l <= v && v <= r) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

 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
32
33
34
35
36
func strobogrammaticInRange(low string, high string) int {
    n := 0
    var dfs func(int) []string
    dfs = func(u int) []string {
        if u == 0 {
            return []string{""}
        }
        if u == 1 {
            return []string{"0", "1", "8"}
        }
        var ans []string
        pairs := [][]string{{"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"}}
        for _, v := range dfs(u - 2) {
            for _, p := range pairs {
                ans = append(ans, p[0]+v+p[1])
            }
            if u != n {
                ans = append(ans, "0"+v+"0")
            }
        }
        return ans
    }
    a, b := len(low), len(high)
    l, _ := strconv.Atoi(low)
    r, _ := strconv.Atoi(high)
    ans := 0
    for n = a; n <= b; n++ {
        for _, s := range dfs(n) {
            v, _ := strconv.Atoi(s)
            if l <= v && v <= r {
                ans++
            }
        }
    }
    return ans
}

Comments