Cracking the coding interview--Q8.4

题目

原文：

Write a method to compute all permutations of a string.

译文：

写一个方法返回一个字符串的所有排列。

解答

显然对于一个长度为n的串，它的全排列共有A(n, n)=n!种，由递归的方法解，若字符串是“abc”,函数名为recursionPermu，由不同的递归思路分析。

解法一：

将第0个字符a取出,递归调用recursionPermu求出剩余串"bc"的所有排列，为"bc","cb",再分别针对此字符串进行插空得到全部排列：abc,bac,bca,acb,cab,cba,代码如下：

public static LinkedList
  
    recursionPermu(String str){
		LinkedList
   
     result=new LinkedList
    
     (); if(str.equals("")){ result.add(""); return result; } String c=str.substring(0,1); LinkedList
     
       res=recursionPermu(str.substring(1)); for(int i=0;i
      
       
 解法二： 
       
 
       
另外可以依次取字符串的每个字符，然后用recursionPermu递归求出剩余串的排列数，再在每个排列前加上该字符即可，如abc的所有排列：abc,acb,bac,bca,cab,cba，代码如下：
 
       
 
       
public static LinkedList
        
          recursionPermu1(String str){
		LinkedList
         
           result=new LinkedList
          
           (); if(str.equals("")){ result.add(""); return result; } for(int i=0;i
           
             res=recursionPermu1(eraseStr(t,i)); for(int j=0;j
            
             
 完整代码如下： 
             
 
             
 
             
import java.util.LinkedList;

class Q8_4{
	public static LinkedList
              
                recursionPermu(String str){
		LinkedList
               
                 result=new LinkedList
                
                 (); if(str.equals("")){ result.add(""); return result; } String c=str.substring(0,1); LinkedList
                 
                   res=recursionPermu(str.substring(1)); for(int i=0;i
                  
                    recursionPermu1(String str){ LinkedList
                   
                     result=new LinkedList
                    
                     (); if(str.equals("")){ result.add(""); return result; } for(int i=0;i
                     
                       res=recursionPermu1(eraseStr(t,i)); for(int j=0;j
                      
                        res=recursionPermu(s); for(int i=0;i
                       
                         res1=recursionPermu1(s); for(int i=0;i
                        
                         
 ---EOF---