StrobogrammaticNumber II

题目描述

解题方法

Solution

class Solution(object):
    s_map = {
        "0":"0",
        "1":"1",
        "8":"8"
        }
    d_map = {
        "0":"0",
        "1":"1",
        "6":"9",
        "8":"8",
        "9":"6"
        }
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if not n:
            return []
        if n == 1:
            return ["0", "1", "8"]
        if n == 2:
            return ["11","69","88","96"]

        result = []

        self.findHelper(result, "", "", 1, n)

        return result

    def findHelper(self, result, left_str, right_str, start, end):
        if start == end: # only one character left
            for c in self.s_map:
                new_str = left_str + c + right_str
                result.append(new_str)
            return
        elif start + 1 == end:
            for c in self.d_map:
                new_str = left_str + c + self.d_map[c] + right_str
                result.append(new_str)
            return
        # start and end
        for c in self.d_map:
            if start == 1 and c == "0":
                continue
            left_str += c
            right_str = self.d_map[c] + right_str
            self.findHelper(result, left_str, right_str, start+1, end-1)
            left_str = left_str[:-1]
            right_str = right_str[1:]

Reference