028. 字符串排列

　　题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 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

Solutions

References