Strobogrammatic Number Ii - Leetcode Solution

Strobogrammatic Number II is a popular problem on LeetCode. It belongs to the category of Backtracking. The problem statement is as follows:

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are a number of length n.

For example, Given n = 2, return ["11","69","88","96"].

One way to solve this problem is to backtrack through all the possible combinations of strobogrammatic numbers of length n. To do this, we start building the number from left to right. For each position, we add all possible strobogrammatic numbers, and then recursively generate the following positions.

We can keep track of the current number by using a variable that contains the string of the number. At each recursion, we add a digit to this string and check whether the length of the string is equal to n.

We also need to check that the first and last digits of the number match the corresponding strobogrammatic pair. If they do not, we stop the recursion and move back up to the previous level.

At the end of each recursion, we add the valid strobogrammatic numbers to a list, which we return at the end.

Here is the code to solve this problem:

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        strobogrammatic_pairs = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
        result = []
        current_number = [""] * n
        
        def backtrack(start, end):
            if start > end:
                result.append("".join(current_number))
                return
            
            for pair in strobogrammatic_pairs:
                if start == end and pair not in ("0", "1", "8"):
                    continue
                
                current_number[start] = pair
                current_number[end] = strobogrammatic_pairs[pair]
                
                if start != end or pair == strobogrammatic_pairs[pair]:
                    backtrack(start + 1, end - 1)
        
        backtrack(0, n - 1)
        return result

The time complexity of this algorithm is O(5^(n/2)), since we have to generate all possible combinations of n/2 digits, and for each digit we have 5 possibilities (0, 1, 6, 8, 9). The space complexity is O(n), since we need to store the current number at each recursion level.

1