原标题：剑指Offer（二十七）：字符串的排列

原文来自：CSDN      原文链接：https://blog.csdn.net/baidu_31657889/article/details/100523657

一、引子

这个系列是我在牛客网上刷《剑指Offer》的刷题笔记，旨在提升下自己的算法能力。
查看完整的剑指Offer算法题解析请点击CSDN和github链接：
剑指Offer完整习题解析CSDN地址
github地址

二、题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

1、思路

递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。

(1) 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）；
(2) 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。

2、编程实现

python

代码实现方案：

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if len(ss) <=1:
            return ss
        res = set()
        #  遍历字符串，固定第一个元素，第一个元素可以取a,b,c...，然后递归求解
        for i in range(len(ss)):
            # 使用排序算法 字符串是除了固定的那个字符 依次固定了元素，其他的全排列（递归求解）
            for j in self.Permutation(ss[:i]   ss[i 1:]):
                # 集合添加元素的方法add(),集合添加去重（若存在重复字符，排列后会存在相同，如baa,baa）
                res.add(ss[i]   j)
        # sorted()能对可迭代对象进行排序,结果返回一个新的list
        return sorted(res)

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com