LeetCode 247. Strobogrammatic Number II

Description

https://leetcode.com/problems/strobogrammatic-number-ii/

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

Find all strobogrammatic numbers that are of length = n.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

Explanation

recursive

Python Solution

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
    
        return self.helper(n, n)
        
        
    def helper(self, current_length, n):
        if current_length == 0:
            return [""]
        
        if current_length == 1:
            return ["0", "1", "8"]
        
        
        result = []
        subs = self.helper(current_length - 2, n)
        
        for sub in subs:
            if current_length != n:
                result.append("0" + sub + "0")
            result.append("6" + sub + "9")
            result.append("9" + sub + "6")
            result.append("8" + sub + "8")
            result.append("1" + sub + "1")
            
        return result
  • Time Complexity: ~N
  • Space Complexity: ~N

Leave a Reply

Your email address will not be published.