First they ignore you
then they ridicule you
then they fight you
then you win
    -- Mahatma Gandhi
Chinese => English     英文 => 中文             
随笔-221  评论-1047  文章-0  trackbacks-0
今天看到迅雷的一个笔试题,一时手痒,便拿来试试,具体题目是这样的:
请打印出一个字符串中所有字母的全排列结果,比如输入字符串abc,则打印出abc, acb, bac, bca, cab, cba

下面是我的解法,由于时间仓促,没有仔细研究,无法保证这是最优的

package  edu.ecust.test;

import  java.util.ArrayList;
import  java.util.Iterator;
import  java.util.List;

public   class  Test  {
    
public   static   void  main(String[] args)  {
        System.out.println(range(
" abc " ));
    }

    
    
public   static  List < String >  range(String str)  {
        
if  ( 1   ==  str.length())  {
            List
< String >  result  =   new  ArrayList < String > ();
            result.add(str);
            
return  result;
        }

        
        
char [] chars  =  str.toCharArray();
        
        List
< String >  result  =   new  ArrayList < String > ();
        
for  ( int  i  =   0 , n  =  chars.length; i  <  n; i ++ {
            
char [] swapedChars  =  swapElems(i, chars);
            
char  c  =  swapedChars[ 0 ];
            
char [] remainChars  =   new   char [swapedChars.length  -   1 ];
            System.arraycopy(swapedChars, 
1 , remainChars,  0 , swapedChars.length  -   1 );
            String remainStr 
=   new  String(remainChars);
            List
< String >  partialResult  =  range(remainStr);
            
            
for  (Iterator < String >  it  =  partialResult.iterator(); it.hasNext(); )  {
                result.add(c 
+  it.next());
            }

        }

        
        
return  result;
    }

    
    
public   static   char [] swapElems( int  index,  char [] array)  {
        
char [] chars  =   new   char [array.length];
        System.arraycopy(array, 
0 , chars,  0 , array.length);
        
char  c  =  chars[index];
        
for  ( int  i  =  index  -   1 ; i  >=   0 ; i -- {
            chars[i 
+   1 =  chars[i];
        }

        chars[
0 =  c;
        
return  chars;
    }

}
posted on 2006-11-03 19:07 山风小子 阅读(3068) 评论(5)  编辑  收藏 所属分类: Algorithm