剑指Offer(二十七):字符串的排列

2017年12月19日10:19:12 4 7,271 °C
摘要

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

剑指Offer(二十七):字符串的排列

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

输入描述:

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

1、思路

我们求整个字符串的排列,可以看成两步:首先求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符交换。如下图所示:

剑指Offer(二十七):字符串的排列

上图就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符,求后面所有字符的排列。这个时候我们仍把后面的所有字符分为两部分:后面的字符的第一个字符,以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

这个思路,是典型的递归思路。

2、代码

C++:

Python:

Python:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  3   博主  1

    • avatar no more United Kingdom 谷歌浏览器 Windows 10 英国 0

      void PermutationCore(string str, int begin){}
      这里的str加不加&结果会不同,为什么呢?

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

          @no more &是取值啊,用的是地址。

        • avatar luweikxy 来自天朝的朋友 谷歌浏览器 Mac OS X 10_13_6 中国 移动 0

          //位置交换
          swap(str[begin], str[i]);
          //递归调用,前面begin+1的位置不变,后面的字符串全排列
          PermutationCore(str, begin + 1);
          // 位置应该再换回来,虽然不加这句也对,但是我觉得还是要加上
          swap(str[begin], str[i]);

          • avatar 锟斤拷锟斤拷小山锟斤拷 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 北京电信互联网数据中心 0

            楼主这个没有去重,答案有误