Leetcode 248. Strobogrammatic Number III

Problem Explanation

A strobogrammatic number is a number that looks the same when it is rotated 180 degrees also known as upside down. In this problem, we are given two numbers represented in the form of strings (low, high). We are required to count and return the number of strobogrammatic numbers in the range of low to high.

Let's take an example. The input is low = "50", high = "100". The strobogrammatic numbers in this range are 69,88, and 96. Hence, the output is 3.

The challenge here is to create an efficient algorithm to count these numbers especially considering the range might be large. Thus, representing numbers as strings organizes our input data more intuitively.

Approach

The solution makes use of depth-first search(DFS). The idea is to generate all possible strobogrammatic numbers of lengths ranging from low.length() to high.length() and checking if the generated numbers fall in the given range.

We initiate our search for numbers of length 'n' by filling the first half of our string s with numbers from pairs (0,0), (1,1), (6,9), (8,8), (9,6), and filling the second half with their corresponding strobogrammatic counterparts. For example, if (6,9) is chosen to fill s[0] in the first half, then s[n - 1] in the second half is filled by number 9.

While generating numbers, we ensure first digit is not 0(unless the number is 0 itself), and if we are filling the middle digit of an odd length number, it must be 0,1 or 8 as only these numbers remain the same after rotating.

The checking if the generated number(M) is in range low(L) to high(H) involves some steps:

• If M, L, and H are of same length, then M should not be less than L AND M should not be greater than H.
• If M and L are of same length, then M should not be less than L.
• If M and H are of same length, then M should not be greater than H.

Algorithm Steps

• For each length from low.length to high.length,
  • Generate all strobogrammatic numbers of this length and check if they lie in the given range.
• Return the count of strobogrammatic numbers lying in the given range low to high.

Solution

Let's see the solution in different programming languages.

1
2python
3#Python Solution
4
5class Solution:
6    def strobogrammaticInRange(self, low: str, high: str) -> int:
7        self.count = 0
8        self.pairs = [('0','0'),('1','1'),('6','9'),('8','8'),('9', '6')]
9        for l in range(len(low), len(high) + 1):
10            self.dfs(low, high, [''] * l, 0, l - 1)
11        return self.count
12
13    def dfs(self, low, high, c, left, right):
14        if left > right:
15            s = ''.join(c)
16            if len(s) == len(low) and s < low or len(s) == len(high) and s > high:
17                return
18            self.count += 1
19        for p in self.pairs:
20            c[left], c[right] = p[0], p[1]
21            if c[0] == '0' and len(c) != 1 or left < right and c[left] == '6' and c[right] == '9' or c[left] == '9' and c[right] == '6':
22                continue
23            if left < right or left == right and p[0] == p[1]:
24                self.dfs(low, high, c, left + 1, right - 1)

1
2java
3//Java Solution
4
5class Solution {
6    private int count = 0;
7    private char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'9', '6'}, {'8', '8'}};
8    public int strobogrammaticInRange(String low, String high) {
9        for (int len = low.length(); len <= high.length(); len++) {
10            char[] c = new char[len];
11            dfs(low, high, c, 0, len - 1);
12        }
13        return count;
14    }
15
16    private void dfs(String low, String high, char[] c, int left, int right) {
17        if (left > right) {
18            String s = new String(c);
19            if ((s.length() == low.length() && s.compareTo(low) < 0) || 
20                (s.length() == high.length() && s.compareTo(high) > 0)) return;
21            count++;
22            return;
23        }
24
25        for (char[] pair : pairs) {
26            c[left] = pair[0];
27            c[right] = pair[1];
28            if (c.length != 1 && c[0] == '0') continue;
29            if (left < right || (left == right && pair[0] == pair[1])) {
30                dfs(low, high, c, left + 1, right - 1);
31            }
32        }
33    }
34}

1
2csharp
3//C# Solution
4
5public class Solution {
6    int count;
7    public int StrobogrammaticInRange(string low, string high) {
8        count = 0;
9        var pairs = new char[,]{{'0', '0'},{'1', '1'},{'6', '9'},{'8', '8'},{'9', '6'}};
10        for (int len = low.Length; len <= high.Length; len++) {
11            Dfs(pairs, low, high, new char[len], 0, len - 1);
12        }
13        return count;
14    }
15    
16    private void Dfs(char[,] pairs, string low, string high, char[] c, int left, int right) {
17        if(left > right) {
18            string s = new string(c);
19            if((s.Length == low.Length && string.Compare(s, low) < 0) || 
20                (s.Length == high.Length && string.Compare(s, high) > 0)) return;
21            count++;
22            return;
23        }
24        for(int i = 0; i < pairs.GetLength(0); i++) {
25            c[left] = pairs[i, 0];
26            c[right] = pairs[i, 1];
27            if(c[0] == '0' && c.Length != 1 || 
28                (left != right && c[left] == '6' && c[right] == '9') || 
29                (c[left] == '9' && c[right] == '6')) continue;
30            if(left < right || left == right && pairs[i, 0] == pairs[i, 1]) 
31                Dfs(pairs, low, high, c, left + 1, right - 1);
32        }
33    }
34}

1
2JavaScript
3//JavaScript Solution
4
5var strobogrammaticInRange = function(low, high) {
6    var count = 0;
7    var pairs = [['0', '0'],['1', '1'],['6', '9'],['9', '6'],['8', '8']];
8    for (var len = low.length; len <= high.length; len++) {
9        var c = new Array(len);
10        dfs(low, high, pairs, c, 0, len - 1);
11    }
12    return count;
13    
14    function dfs(low, high, pairs, c, left, right) {
15        if (left > right) {
16            var s = c.join('');
17            if ((s.length === low.length && s < low) || 
18                (s.length === high.length && s > high)) {
19                return;
20            }
21            count++;
22            return;
23        }
24        
25        for (var pair of pairs) {
26            c[left] = pair[0];
27            c[right] = pair[1];
28            if (c[0] === '0' && c.length !== 1 || 
29                (left < right && c[left] === '6' && c[right] === '9') || 
30                (c[left] === '9' && c[right] === '6'))  continue;
31            if (left < right || left === right && pair[0] === pair[1]) {
32                dfs(low, high, pairs, c, left + 1, right - 1);
33            }
34        }
35    }
36};

Runtime Analysis

The time complexity for the above algorithm is O(5^(N/2)), where N is the length of the string. The reason for this complexity is that we are considering all combinations using our five pairs.

The space complexity for our algorithm is O(N), where N is the size of the input string. During every iteration, we populate and store the new characters for the string length represented by N.

Conclusion

This problem allows us to make use of the depth-first search to solve the problem efficiently. It tests our ability to convert mathematical concepts into code effectively. It's also a way of practicing how to manipulate strings and their corresponding characters especially since we are dealing with a large number. The understanding of depth-first search and backtracking is crucial for creating an optimized solution for this problem. Different programming languages have a different syntax, but the basic approach of solving the problem remains the same. Utilizing the characteristics of strobogrammatic numbers and their pairs is the key to a compact and efficient solution.