一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
1、思路
我们求整个字符串的排列,可以看成两步:首先求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符交换。如下图所示:
上图就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符,求后面所有字符的排列。这个时候我们仍把后面的所有字符分为两部分:后面的字符的第一个字符,以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。
这个思路,是典型的递归思路。
2、代码
C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution { public: vector<string> Permutation(string str) { //判断输入 if(str.length() == 0){ return result; } PermutationCore(str, 0); //对结果进行排序 sort(result.begin(), result.end()); return result; } private: void PermutationCore(string str, int begin){ //递归结束的条件:第一位和最后一位交换完成 if(begin == str.length()){ result.push_back(str); return; } for(int i = begin; i < str.length(); i++){ //如果字符串相同,则不交换 if(i != begin && str[i] == str[begin]){ continue; } //位置交换 swap(str[begin], str[i]); //递归调用,前面begin+1的位置不变,后面的字符串全排列 PermutationCore(str, begin + 1); } } vector<string> result; }; |
Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # -*- coding:utf-8 -*- class Solution: def __init__(self): self.result = [] def Permutation(self, ss): # write code here if len(ss) == 0: return [] self.PermutationCore(ss, 0) sorted(self.result) return self.result def PermutationCore(self, str_, begin): if begin == len(str_): self.result.append(str_) return for i in range(begin, len(str_)): if i != begin and str_[i] == str_[begin]: continue str_list = list(str_) str_list[i], str_list[begin] = str_list[begin], str_list[i] str_ = ''.join(str_list) self.PermutationCore(str_, begin+1) |
Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # -*- coding:utf-8 -*- class Solution: def Permutation(self, ss): if len(ss) <=0: return [] res = list() self.perm(ss,res,'') uniq = list(set(res)) return sorted(uniq) def perm(self,ss,res,path): if ss=='': res.append(path) else: for i in range(len(ss)): self.perm(ss[:i]+ss[i+1:],res,path+ss[i]) |
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2019年9月29日 下午6:57 沙发
void PermutationCore(string str, int begin){}
这里的str加不加&结果会不同,为什么呢?
2019年10月8日 上午9:25 1层
@no more &是取值啊,用的是地址。
2020年2月9日 下午12:51 板凳
//位置交换
swap(str[begin], str[i]);
//递归调用,前面begin+1的位置不变,后面的字符串全排列
PermutationCore(str, begin + 1);
// 位置应该再换回来,虽然不加这句也对,但是我觉得还是要加上
swap(str[begin], str[i]);
2021年4月19日 下午2:09 地板
楼主这个没有去重,答案有误