黑马程序员技术交流社区

标题: 请高手分析一下这段代码的思路 [打印本页]

作者: 湛添友 时间: 2014-5-6 08:25
标题: 请高手分析一下这段代码的思路

//打印一个字符串及任意子串的任意排序
public class test
{
      public static void main(String[] args)
      {
            showPermString("abcd");
      }



      public static void showPermString(String str)
      {
            for(int i=1; i<=str.length(); i++)
            {
                     List<String> list = new ArrayList<String>();
                     perm(list, str.toCharArray(), 0, i);
                     System.out.println(list);
            }
      }




      public static void perm(List<String> list,char[] chs,int k,int len)
      {
            if(k == chs.length)
            {
                     String string = String.valueOf(chs, 0, len);
                     if(!list.contains(string))
                              list.add(string);
            }
            else
            {
                     for(int i=k; i<chs.length; i++)
                     {
                              swap(chs, i, k);
                              perm(list,chs, k+1,len);
                              swap(chs, i, k);
                     }
            }

      }

      public static void swap(char[] chs,int i,int j)
      {
            char tem = chs[i];
            chs[i] = chs[j];
            chs[j] = tem;
      }

}

作者: 神马 时间: 2014-5-6 10:11
我也是看了很久才明白，没有注释害死人啊。。。编程时是正的理解容易，看程序就要逆推了额。
首先这个程序是用递归实现字符串及其子串的全排列。其实只要理解了perm方法其他的就差不多了。perm使用递归实现一个字符串的全排列。然后showPermString方法每次循环截取一定的长度，就成了它相应子串的全排列。也就是说它求子串全排列的时候，也是把整串的全排列求出来，截取从0到len的一段，因为整串的全排列肯定包含了其所有子串的全排列。但是这样效率很低。正好我的基础测试就是这个，我把我的代码给你看看。当字符串在“abcdefghi”这样长度的时候，两个程序的速度差距就很明显了。

package com.itheima;
/**
* 第五题：编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如：
* 原始字符串是"abc"，打印得到下列所有组合情况：
* "a" "b" "c"
* "ab" "bc" "ca" "ba" "cb" "ac"
* "abc" "acb" "bac" "bca" "cab" "cba"
* @author JunZhu
*/
import java.util.ArrayList;
public class Test5 {
public static void main(String[] args){
//创建一个字符串，并调用allGroups方法输出其全字符组合
String s="abc";
System.out.println(s+"的全字符排列组合为：");
allGroups(s);
}
//创建一个方法，用于输出指定字符串的全字符组合
public static void allGroups(String s){
//把字符串转换为字符数组
char[] c=s.toCharArray();
int l=s.length();
String[] sc=new String[l];
//创建一个ArrayList字符串容器al
ArrayList<String> al=new ArrayList<String>();
//给集合al和字符串数组sc赋初始值
for(int a=0;a<l;a++){
sc[a]=String.valueOf(c[a]);
al.add(sc[a]);
}
//while循环，判断条件为组合的长度是否到了最大值
while(al.get(al.size()-1).length()<l){
//al2用于临时存放当前长度的字符串的所有可能组合
ArrayList<String> al2=new ArrayList<String>();
//for循环表示，当首字符为sc[i]时，当前长度字符串的所有可能组合
for(int i=0;i<l;i++){
//这个增强for循环用来取al中的字符串，当满足不重复的条件时，就与首字符sc[i]进行组合
for(String s1:al){
if(s1.contains(sc[i])||al.get(al.size()-1).length()!=s1.length()) continue;
al2.add(sc[i]+s1);
}
}
//将当前长度字符串的所有组合存入al中，之后进入下一个长度的排列组合
for(String s2 : al2) al.add(s2);
}
//输出al中的所有组合，由于ArrayList是有序的，因此可以按照组合字符串中字符个数按行输出
int b=1;
for(String s3:al){
if(s3.length()!=b) System.out.println();
System.out.print(s3+"\t");
b=s3.length();
}
}
}

复制代码

作者: jieyu90 时间: 2014-5-6 10:35
Mark，等会回来看看

作者: renshu16 时间: 2014-5-6 14:04
学习了，很详细

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2