247.Strobogrammatic Number II

Tags: [permutation], [recursion], [string]

Com: {g}

Link: https://leetcode.com/problems/strobogrammatic-number-ii/#/description

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.

For example,
Given n = 2, return["11","69","88","96"].

Solution: Permutation

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n <= 0:
            return []
        if n == 1:
            return ['0', '1', '8']

        chars = ['0', '1', '6', '8', '9']
        buff = []
        result = []
        self.find_strobogrammatic_helper(n, chars, buff, result)
        return result

    def find_strobogrammatic_helper(self, n, chars, buff, result):
        # base case
        if len(buff) == n / 2:
            if n % 2 == 0:
                result.append(self.supplement(n, buff))
            else:
                for c in ['0', '1', '8']:
                    buff.append(c)
                    result.append(self.supplement(n, buff))
                    buff.pop()
            return

        for i in xrange(len(chars)):
            if not buff and chars[i] == '0':
                continue

            buff.append(chars[i])
            self.find_strobogrammatic_helper(n, chars, buff, result)
            buff.pop()

    def supplement(self, n, buff):
        chars = {
            '0': '0',
            '1': '1',
            '6': '9',
            '8': '8',
            '9': '6'
        }
        right = [chars[x] for x in buff]
        if n % 2 != 0:
            right = right[:-1]

        right = right[::-1]
        result = list(buff) + right
        return ''.join(result)

Revelation:

• Each time, we just focus on building half of string, then we can generate the right half based on the left half.
• One char can be used multiple times, so when we do the permutation, we didn't use index_set().
• '0' can be used to build the string, unless it is a leading 0.

Note:

• Time complexity = O(5^(n/2) * n).

Another Solution:

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        buff = [None for _ in xrange(n)]
        self.helper(buff, 0, n - 1, result)
        return result

    def helper(self, buff, start, end, result):
        # base case
        if start > end:
            result.append(''.join(buff))
            return
        if start == end:
            for c in ['0', '1', '8']:
                buff[start] = c
                self.helper(buff, start + 1, end - 1, result)
            return

        if start != 0:
            buff[start] = '0'
            buff[end] = '0'
            self.helper(buff, start + 1, end - 1, result)

        chars = {
            '1': '1',
            '6': '9',
            '9': '6',
            '8': '8'
        }
        for c in chars:
            buff[start] = c
            buff[end] = chars[c]
            self.helper(buff, start + 1, end - 1, result)

Revelation:

• We must put the buff string into result, when start > end, think about the case n = 2,

Note:

• Time complexity = O(5^n).