DP solution with explanation.


  • 0
    S

    Here are the steps:

    • For single-digit strobogrammatic numbers, where n = 1, just return ['0', '1', '8']

    • When n >= 2, let's simplify this problem to have invalid strobogrammatic numbers, which are multiple "0"s, like "00", "000", "0000".

    • The strobogrammatic numbers for n = 2 will be: ['11', '69', '96', '88', '00']. Then for any strobogrammatic number with n > 2, it could be derived by inserting a strobogrammatic number with a length of n - 2 into the middle of the number in this list.
      For example, if n = 3, we insert '0', '1' and '8' into ['11', '69', '96', '88', '00'] respectively, we will have:
      0 into 11: 101
      1 into 11: 111
      8 into 11: 181
      ...

    • Then this becomes a dp problem. Say dp[i] is the list of all the strobogrammatic numbers for n = i, then we should have dp[i] = {elements derived by inserting every element in dp[i - 2] into the base list ['11', '69', '96', '88', '00']}

    • Finally we get rid of those invalid strobogrammatic numbers for dp[n], which are the strings start with "0"

    • I used last_list and result_list in the code to store the list because we only care about the two most recent results.

    class Solution(object):
        def findStrobogrammatic(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            if n <= 0:
                return []
            if n == 1:
                return ['0', '1', '8']
            base_list = ['11', '69', '96', '88', '00']
            last_list = ['0', '1', '8']
            result_list = ['11', '69', '96', '88', '00']
            for i in xrange(2, n):
                temp_list = []
                for base_num in base_list:
                    for insert_num in last_list:
                        curr_num = base_num[0] + insert_num + base_num[1]
                        temp_list.append(curr_num)
                last_list = result_list
                result_list = temp_list
            return [num for num in result_list if num[0] != '0']
    

Log in to reply
 

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