package test;
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
String str = "abcdef";
List<String> list = new Test().completeArray(str, 0);
System.out.println(list);
System.out.println("there are " + list.size() + " kinds of groups.");
}
public List<String> completeArray(String str, int index) {
if (index == str.length() - 1) {
List<String> list = new ArrayList<String>();
list.add(String.valueOf(str.charAt(index)));
return list;
}
List<String> newLists = new ArrayList<String>();
List<String> oldLists = completeArray(str, index + 1);
for (String oldString : oldLists) {
char c = str.charAt(index);
for (int i = 0; i <= oldString.length(); i++) {
newLists.add(Insert2Str(oldString, i, c));
}
}
return newLists;
}
private String Insert2Str(String str, int i, char c) {
if(str == null){
return String.valueOf(c);
}else {
return str.substring(0, i) + c + str.substring(i);
}
}
}
思路是递归,要取str的全排列,只要取后n-1位的全排列,再把第1位往里面插入,就ok了。递归的终止是,游标index扫描到最后一位,只有一个字母的时候排列之后一种,开始return
产生新字符串那地方,刚开始的时候用ArrayList的add方法,但是这样的话有太多的转换类型操作,代码显得很乱,看着很不爽,就写了一个Insert2Str的方法,往字符换的指定位置插入一个字符。
代码存在效率问题,大概到8个字母以上运行就很慢了,10几位的话会报java.lang.OutOfMemoryError异常,求问题所在,和更好的算法
分享到:
相关推荐
简单的实现,代码很短。...输入一个字符串,输出它的字符的所有组合的情况 如输入“abc”,则输出abc,acb,bac,bca,cab,cba。 但如果输入“aba”,即有重复的,也会输出aba,aab,baa,baa,aba,aab。
例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路 这是典型的递归求解问题,递归算法有四个特性: 必须有可达到的终止条件,否则程序陷入死循环 子问题在规模上...
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 输入 输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在2到8之间。 输出 输出这个字符串的所有排列方式,每行一个排列。...
下面小编就为大家带来一篇js实现字符全排列算法的简单方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
插入排序、一个英文句子单词逆转,字符串循环移位、去重、全排列算法(递归和非递归实现)、KMP算法
求任意一个字符串的全排列组合,例如a=’123′,输出 123,132,213,231,312,321。(暂时假定字符串没有重复) 解决方案 目前有两种解决的方法 方法一: def str_sort(s=''): if len(s) <= 1: return [s]...
组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法
算法课写的小程序,在字典序下对输出序列的全排列
下面小编就为大家带来一篇js-FCC算法-No repeats please字符串的全排列(详解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
第一章 字符串 o 1.0 本章导读 o 1.1 旋转字符串 o 1.2 字符串包含 o 1.3 字符串转换成整数 o 1.4 回文判断 o 1.5 最长回文子串 o 1.6 字符串的全排列 o 1.10 本章习题 第二章 数组 o 2.0 本章导读 o 2.1 寻找最小的...
主要介绍了C#求数组中元素全排列的方法,较为详细的分析了数组全排列算法的原理与实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
第一章 字符串1.0 本章导读1.1 旋转字符串1.2 字符串包含1.3 字符串转换成整数1.4 回文判断1.5 最长回文子串1.6 字符串的全排列1.10 本
第一章 字符串1.0 本章导读1.1 旋转字符串1.2 字符串包含1.3 字符串转换成整数1.4 回文判断1.5 最长回文子串1.6 字符串的全排列1.10 本
LeetCode判断字符串是否循环 Data-Structures-and-Algorithms 记录学习数据结构与算法的笔记 刷题记录在leetcode目录下 链表相关题目 19: 删除链表倒数第 n 个结点 21: 合并两个有序链表 141: 判断链表中是否有环 ...
: 字典树,用于高效存储、查找字符串单词。 : 能够获取大顶堆、小顶堆以及TopK过滤器。 : 给定一个序列,求按字典序的下一个排列。 : 洗牌算法,即把一个列表随机打乱。 : 列表旋转和移动。 : B树,支持CURD操作。 :...
12. 字符串匹配(KMP算法) 13. 全排列,全组合 14. 二维线段树 15. 稳定婚姻匹配 16. 后缀数组 17. 左偏树 18. 标准RMQ-ST 19. 度限制最小生成树 20. 最优比率生成树(0/1分数规划) 21. 最小花费置换 22. 区间K大数 23....
1. 前言 本文介绍了常用的排列组合算法,包括全排列算法,全组合...生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有字典顺序中相邻的字符串。这就要求这一个与下一个有尽可能长的共同前缀,