# DP solution with explanation.

• 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']
``````

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