Strobogrammatic Number II

To find all strobogrammatic numbers of length n, we can build the numbers recursively, using the strobogrammatic pairs '0' and '0', '1' and '1', '6' and '9', '8' and '8', '9' and '6'. However, we should avoid using '0' at the beginning and end of the numbers.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        return self.helper(n, n)

    def helper(self, n: int, m: int) -> List[str]:
        if n == 0:
            return [""]
        if n == 1:
            return ["0", "1", "8"]

        previous_numbers = self.helper(n - 2, m)
        result = []

        for number in previous_numbers:
            if n != m:
                result.append("0" + number + "0")
            result.append("1" + number + "1")
            result.append("6" + number + "9")
            result.append("8" + number + "8")
            result.append("9" + number + "6")

        return result

The function helper recursively constructs the strobogrammatic numbers. It is called with two parameters n and m, where n is the current length for which the strobogrammatic numbers are being generated, and m is the original length.

Here’s how it works:

  • Base cases: If n is 0, it returns an empty string. If n is 1, it returns the strobogrammatic numbers of length 1.
  • Recursively calls helper for n-2 and builds the strobogrammatic numbers of length n based on that.
  • Skips adding “0” at the beginning and end if n is equal to m.

The time complexity of this function is O(5^(n/2)), as there are five choices for each pair of digits, and the recursion goes down to n/2 levels. The space complexity is O(n), due to the recursive function call stack.

 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

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        return self.helper(n, n)

    def helper(self, n: int, m: int) -> List[str]:
        if n == 0:
            return [""]
        if n == 1:
            return ["0", "1", "8"]

        list = self.helper(n - 2, m)

        res = []

        for i in range(len(list)):
            s = list[i]

            if n != m:
                res.append("0" + s + "0")

            res.append("1" + s + "1")
            res.append("6" + s + "9")
            res.append("8" + s + "8")
            res.append("9" + s + "6")

        return res