给定hello则它的全排列共有 5*4*3*2*1/ (2*1)=60种。
思想(先不考虑去重复):
首先取第一个字符如h,然后计算剩下4个字符ello的全排列,然后再将h和这些全排列相加就OK了,然后再取第二个... 第三个...,典型的循环+递归思想。
如果要去重,可以考虑先将整个字符串排序,hello -> ehllo,在循环的时候,首先判断当前字符和前一个字符是否相同,如果相同则说明这个字符已经处理,跳过即可。
java code:
@Test
public void run()
{
String str = "hello";
char[] array = str.toCharArray();
Arrays.sort(array);
List<String> result = this.compose(array);
System.out.println(result.size());
for (String s : result)
{
System.out.println(s);
}
}
private List<String> compose(char[] array)
{
List<String> result = new LinkedList<String>();
if (array.length == 1)
{
result.add(String.valueOf(array[0]));
return result;
}
for (int i = 0; i < array.length; i++)
{
char ch = array[i];
//if the current character is the same with previous one, it means this character has been arranged, skip it
if (i > 0 && ch == array[i - 1])
{
continue;
}
List<String> subList = this.compose(this.getSubarray(array, i));
for (String str : subList)
{
result.add(String.valueOf(ch) + str);
}
}
return result;
}
private char[] getSubarray(char[] array, int exclude)
{
char[] sub = new char[array.length - 1];
System.arraycopy(array, 0, sub, 0, exclude);
System.arraycopy(array, exclude + 1, sub, exclude, array.length - exclude - 1);
return sub;
}
复杂度: N!
分享到:
相关推荐
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
Java写的源码,解决各种字符串全排列问题,已解决重复问题,经过上机调试可直接运行
可以打印出字符串的全排列,代码是C语音风格的,刚学习编程时写的代码
输出有重复字符的全排列,C++源码......
输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路 这是典型的递归求解问题,递归算法有四个特性: 必须有可...
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
简单的实现,代码很短。...输入一个字符串,输出它的字符的所有组合的情况 如输入“abc”,则输出abc,acb,bac,bca,cab,cba。 但如果输入“aba”,即有重复的,也会输出aba,aab,baa,baa,aba,aab。
CC++全排列..1--n的全排列以及字符串的全排列
找出一个字符串中出现次数最多的子字符串,并返回重复次数。使用java编写
java接收用户输入的一个字符串和一个字符,将字符串中出现的所有该字符删除,打印新生成的字符串。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。下面给出...
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符...试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。
java JAVA数组与字符串,编写图形界面的程序,接收用户输入的一个字符串和一个字符,将字符串中出现的所有该字符删除,打印新生成的字符串。 String 类或StringBuffer类 deleteCharAt方法
输入一个字符串,字符串由字母、数字组成,可能包含重复的字符。生成这些字符的不重复的全排列,并将结果打印到标准输出上。 【输入形式】 从标准输入上读入一个由字母、数字组成的字符串,字符串的长度小于...
去掉重复的字符串及在第一个字符串中删除在第二个字符串中出现的字符两个程序,vs2013已经验证
主要介绍了Python字符串的全排列算法,结合实例形式较为详细的总结分析了Python字符串全排列的常见操作技巧,需要的朋友可以参考下
传入一个字符串和整数m,将此字符串中从第m个字符开始的全部字符复制成为另一个字符串并打印出来。
输入一个字符串,统计出这个字符串的英文大写字母、小写字母、数字、空格以及其它字符的个数
c#字符串函数练习题,提供一个函数,将用户提供的一个字符串重复n遍,形成一个新的字符串,列如:一个字符串为ABC123重复两遍为ABC123ABC123 此程序使用vs2015c#控制台应用程序平台写的,希望可以帮助你!