难度: Medium
Submission
运行时间: 43 ms
内存: 26.5 MB
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
def dfs(u):
if u == 0:
return ['']
if u == 1:
return ['0', '1', '8']
ans = []
for v in dfs(u - 2):
for l, r in ('11', '88', '69', '96'):
ans.append(l + v + r)
if u != n:
ans.append('0' + v + '0')
return ans
return dfs(n)
Explain
这个题解使用了深度优先搜索（DFS）的思路来生成中心对称数。首先，对于长度为0和1的中心对称数，直接返回对应的结果。对于长度大于1的中心对称数，通过递归生成长度减2的中心对称数，然后在两边添加对称的数字对（11、88、69、96）得到新的中心对称数。特别地，如果当前生成的中心对称数长度不等于目标长度n，还可以在两边添加00得到新的中心对称数。最终返回长度为n的所有中心对称数。
时间复杂度: O(5^(n/2))
空间复杂度: O(n * 5^(n/2))
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
def dfs(u):
if u == 0:
return ['']
if u == 1:
return ['0', '1', '8']
ans = []
for v in dfs(u - 2):
for l, r in ('11', '88', '69', '96'):
ans.append(l + v + r) # 在两边添加对称的数字对
if u != n:
ans.append('0' + v + '0') # 如果当前长度不等于目标长度，可以在两边添加00
return ans
return dfs(n)
Explore
深度优先搜索（DFS）适用于这个问题，因为我们需要探索所有可能的中心对称数组合，直到达到指定的长度。DFS允许从内部向外递归构建对称数，从中心开始向两端扩展，这种自顶向下的构建方法在逻辑上更直观。相对于BFS，DFS在这种情况下可以更自然地遵循生成对称数的递归模式。而动态规划不适用于这种类型的问题，因为中心对称数的生成不涉及到子问题的最优解决策略，而是单纯的组合生成。
正确，这个条件是为了避免生成的中心对称数以0开头，因为在大多数数字表示中，以0开头的数字是不合法或不符合预期的（例如，'01'通常被视为简单的'1'）。如果在长度等于n的最终结果中包含以0开头的数字对，这将导致不正确或无效的输出。因此，这个条件确保只有在生成中间步骤的较短数字时才添加'00'，而在生成最终长度的数字时不会添加以0开头的组合。
这些对称的数字对被选择是因为它们在旋转180度后可以保持视觉上的对称性。例如，'88'旋转后仍然是'88'，而'69'和'96'旋转后会变成彼此。这是中心对称数的基本要求，即数字旋转180度后应该看起来与原数字相同或成为对应的另一个数字。在数学或编程上，这些对没有特别的性质，它们只是单纯满足视觉上的对称要求。
为了减少递归深度或完全避免递归，可以使用迭代方法来生成中心对称数。具体来说，可以从已知的最小长度中心对称数开始，如长度为0和1的情况，然后迭代地向这些数的两端添加对称的数字对来构造更长的数字。这种方法利用循环而非递归，通过维护一个当前所有可能结果的列表，并在每次迭代中更新这个列表，直到达到目标长度。这样可以有效避免递归导致的栈溢出问题。