剑指offer第二版-38.2.字符串的组合

本系列导航:剑指offerjava实现导航帖]()

本系列导航:剑指offerjava实现导航帖

面试题38:字符串的排列

面试题:字符串的组合

题目要求:输入一个字符串,打印出该字符串中字符的所有排列。如输入abc,则打印abc,acb,bac,bca,cab,cba。

题目要求:输入一个字符串,打印出该字符串中字符的所有组合。如输入abc,则打印a,b,c,ab,ac,bc,abc。

解题思路:排列与组合是数学上的常见问题。解题思路与数学上求排列总数类似:首先确定第一个位置的元素,然后一次确定每一个位置,每个位置确实时把所有情况罗列完全即可。以abc为例,我之前更习惯于设置三个空,然后选择abc中的元素放入上述的空中。而书中给的思路是通过交换得到各种可能的排列,具体思路如下:

解题思路:这道题目是在38题.字符串的排列的扩展部分出现的。排列的关键在于次序,而组合的关键在于状态,即该字符是否被选中进入组合中。对于无重复字符的情况,以a,b,c为例,每一个字符都有两种状态:被选中、不被选中;2*2*2=8,再排除为空的情况,一共有7种组合:

对于a,b,c0与0交换,得a,b,c => 1与1交换,得a,b,c =>2与2交换,得a,b,c => 1与2交换,得a,c,b =>2与2交换,得a,c.b0与1交换,得b,a,c => 1与1交换,得b,a,c =>2与2交换,得b,a,c => 1与2交换,得b,c,a =>2与2交换,得b,c,a0与2交换,得c,b,a => 1与1交换,得c,b,a =>2与2交换,得c,b,a => 1与2交换,得c,a,b =>2与2交换,得c,a.b
abc => abcabc => ababc => acabc => aabc => bcabc => babc => cabc => 空(不作为一种组合情况)

书中解法并未考虑有字符重复的问题。对于有重复字符的情况如a,a,b,交换0,1号元素前后是没有变化的,即从生成的序列结果上看,是同一种排列,因此对于重复字符,不进行交换即可,思路如下:

对于有重复字符的情况,不重复的字符各有两种状态;而重复的字符状态个数与重复次数有关。以a,a,b为例,b有两种状态:被选中、不被选中,a,a有三种状态:被选中2个,被选中1个,不被选中。2*3=6,排除为空的情况,一共有5种组合:

发表评论

电子邮件地址不会被公开。 必填项已用*标注