题目描述:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
Solutions
先要将问题归纳到考察的点,这里将字符串分成两个部分,第一个字母,以及后面的部分。将第一个字母替换成后面部分每一个字母的一个排序。
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
if not ss:
return []
res = []
self.helper(ss, res, '')
return sorted(list(set(res)))
def helper(self, ss, res, path):
if not ss:
res.append(path)
else:
for i in range(len(ss)):
self.helper(ss[:i] + ss[i+1:], res, path + ss[i])
刚开始没有想到这个做法,于是查了下,看到 LeetCode 上有人的解法是用 DFS:
# DFS
def permute(self, nums):
res = []
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
# return # backtracking
for i in xrange(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
有热心人士解释如下:
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
lev, avail, lev_node = 0, nums, []
N = len(nums)
def dfs(lev, avail, lev_node):
if lev == N:
res.append(lev_node)
return
for i in range(len(avail)):
dfs(lev+1, avail[:i]+avail[i+1:], lev_node+[avail[i]])
dfs(lev, avail, lev_node)
return(res)
运行过程:
lev: level of tree, i.e. the length of node
avail: elements available to be combined to form new child node
lev_node: node content
dfs(lev, avail, lev_node)
dfs(0, [1,2,3], [])
|- dfs(1, [2,3], [1])
|- dfs(2, [3], [1,2])
|- ...
|- dfs(2, [2], [1,3])
|- dfs(3, [], [1,3,2])
|- no more
|- dfs(1, [1,3], [2])
|- ...
|- dfs(1, [1,2], [3])
|- ...
或者 avail+lev_node:
[1, 2, 3] []
[2, 3] [1]
[3] [1, 2]
[] [1, 2, 3]
[2] [1, 3]
[] [1, 3, 2]
[1, 3] [2]
[3] [2, 1]
[] [2, 1, 3]
[1] [2, 3]
[] [2, 3, 1]
[1, 2] [3]
[2] [3, 1]
[] [3, 1, 2]
[1] [3, 2]
[] [3, 2, 1]
但是很明显这个方法不怎么好解释。
还有一种写在同一个函数的解法:
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if not ss:
return []
if len(ss)==1:
return list(ss)
pStr=[]
charlist=list(ss)
charlist.sort()
for i in range(len(charlist)):
if i>0 and charlist[i]==charlist[i-1]:
continue
temp=self.Permutation(''.join(charlist[:i])+''.join(charlist[i+1:]))
for j in temp:
pStr.append(charlist[i]+j)
return pStr