题目描述
例子
解法
类似剑指offer的字符串全排列
法1 - 常规DFS,记得设置visited
法2 - DFS, 不需要额外的空间 交换的思想
法3 - 非递归,考虑类似于多叉树的层次遍历BFS。
- 注意DFS时存在列表的浅拷贝问题,所以用temp.pop()而不是temp=temp[:-1], 用res.append(temp[:])而不是res.append(temp)
解法1
常规的DFS思想。
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
visited = [True] * len(nums)
self.dfs(nums, 0, [], res, visited)
return res
def dfs(self, nums, pos, temp, res, visited):
if pos == len(nums):
res.append(temp[:])
return
for i in range(len(nums)):
if visited[i]:
visited[i] = False
temp.append(nums[i])
self.dfs(nums, pos+1, temp, res, visited)
visited[i] = True
temp.pop()
解法2
交换的思想
class Solution(object):
def permute(self, nums):
res = []
self.dfs(nums, 0, res)
return res
def dfs(self, nums, pos, res):
if pos == len(nums):
res.append(nums[:])
for i in range(pos, len(nums)):
nums[pos], nums[i] = nums[i], nums[pos]
self.dfs(nums, pos+1, res)
nums[pos], nums[i] = nums[i], nums[pos]
解法3
非递归,将所有情况的层次遍历画成一颗多叉树。遍历下一层时,遍历num插入已有列表所有位置的情况。
class Solution(object):
def permute(self, nums):
queue = [[]]
for num in nums:
for _ in range(len(queue)):
node = queue.pop(0)
for i in range(len(node)+1): # 插入的位置
queue.append(node[:i] + [num] + node[i:])
return queue
用易懂的变量表示如下
class Solution(object):
def permute(self, nums):
lastPerms = [[]]
for num in nums:
perms = []
for lastPerm in lastPerms:
for i in range(len(lastPerm)+1): # 类似BFS, 前中后三个位置
perms.append(lastPerm[:i] + [num] + lastPerm[i:])
lastPerms = perms
return lastPerms