Python solution with detailed explanation


  • 0
    G

    Solution

    Strobogrammatic Number II https://leetcode.com/problems/strobogrammatic-number-ii/

    Algorithm

    • As long as you understand the properties of Strobogrammatic well, there shouldnt be too much of an issue.
    • There are several cases which need to be worked through.
      * Deriving end from start
      * Impact of n as even and odd
      * Impact of character at index 0 - cannot be zero.
    class Solution(object):
        def helper(self, so_far, start, cnt):
            if cnt == len(so_far):
                self.results.append("".join(so_far))
            else:
                end = len(so_far)-1-start
                if start == end:
                    for x in ("1", "8", "0"):
                        so_far[start] = x
                        self.helper(so_far, start+1, cnt+1)
                else:
                    candidates = ("1", "6", "8", "9") if start == 0 else ("1", "6", "8", "9", "0")
                    for x in candidates:
                        so_far[start] = x
                        so_far[end] = self.smap[x]
                        self.helper(so_far, start+1, cnt+2)
            return
        
        
        def findStrobogrammatic(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            self.smap = {"1":"1", "6":"9", "8":"8", "9":"6", "0":"0"}
            self.results = []
            self.helper([""]*n, 0, 0) 
            return self.results
    

Log in to reply
 

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