【剑指Offer】字符串的排列 解题报告（Python）

标签（空格分隔）： LeetCode

---

题目地址：https://www.nowcoder.com/ta/coding-interviews

题目描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

Ways

很多人使用python的permutation库去做，那么还有什么意义呢？

这个题类似于【LeetCode】46. Permutations 解题报告，要做字符串的全排列。做法是把对字符串中的每个元素都当做起始位置，把其他元素当做以后的位置，然后再同样的进行操作。这样就会得到全排列。

这个题不使用index的原因是，我们认为已经遍历过了的元素过滤掉了，只留下了未遍历的剩余的字符串当做ss。因此，所有的元素遍历完成了，ss也就是空了，就可以结束了。

# -*- 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])

Date

2018 年 3 月 10 日