0247._Strobogrammatic_Number_II.md

247. Strobogrammatic Number II

难度: Medium

刷题内容

原题连接

• 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"]

解题方案

思路 1 - 时间复杂度: O(C ^ N)- 空间复杂度: O(C ^ N)******

观察规律可以得到，我们每次只要在之前短2个的结果外面包上一层即可

1. n = 0, res = ['']
2. n = 1, res = ['0', '1', '8']
3. n = 3, res = ["101","111","181","609","619","689","808","818","888","906","916","986"]
4. n = 4, res = ["1001","1111","1691","1881","1961","6009","6119","6699","6889","6969","8008","8118","8698","8888","8968","9006","9116","9696","9886","9966"]

• '0xxxx0'
• '1xxxx1'
• '6xxxx9'
• '8xxxx8'
• '9xxxx6'

但是我们在最终结果要记得消去leading zero,除非它本身就是zero

时间复杂度和空间复杂度中的C是一个常数

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        def helper(n):
            if n == 0:
                return ['']
            if n == 1:
                return ['0', '1', '8']
            lst = helper(n - 2)
            res = []
            for i, s in enumerate(lst):
                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

        res = []
        for s in helper(n):
            if not (len(s) > 1 and s[0] == '0'):
                res.append(s)
        return res 

思路 2 - 时间复杂度: O(C ^ N)- 空间复杂度: O(C ^ N)******

迭代

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        stack = [''] if n % 2 == 0 else ['0', '1', '8']
        for i in range(n%2+1, n, 2):
            cur = []
            for s in stack:
                cur.append('0' + s + '0')
                cur.append('1' + s + '1')
                cur.append('6' + s + '9')
                cur.append('8' + s + '8')
                cur.append('9' + s + '6')
            stack = cur[:]

        res = []
        for s in stack:
            if not (len(s) > 1 and s[0] == '0'):
                res.append(s)
        return res