Python Recursive Solution


  • 0

    Basically insert 1s, 6 and 9, 9 and 6, 8s, and 0s at the ends of the prev solutions. Recurse by n-2 rather than n-1. Remove non-valid (starts with 0) solutions at the end if not base cases.

    class Solution(object):
        def findStrobogrammatic(self, n):
            res = self.helper(n)
            if n in (0, 1):
                return res
            else:
                return [x for x in res if x[0] != "0"]
    
        def helper(self, n):
            if n == 0:
                return [""]
            if n == 1:
                return ["1", "8", "0"]
            else:
                prev_res = self.helper(n-2)
                new_res = []
                for num in prev_res:
                    new_res.append("1" + num + "1")
                    new_res.append("6" + num + "9")
                    new_res.append("8" + num + "8")
                    new_res.append("9" + num + "6")
                    new_res.append("0" + num + "0")
                return new_res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.