Java程序打印字符串的不同排列

2021年5月14日16:35:52 发表评论 855 次浏览

给定一个字符串str，任务是打印str的所有不同排列。

排列是一组对象的全部或部分的排列，就排列顺序而言。

例如，单词“bat”和“tab”代表了一个相似的三个字母单词的两种不同的排列(或安排)。

例子：

输入：str ="abbb"
输出：[abbb, babb, bbab, bbba]
输入：str ="abc"
输出：[abc, bac, bca, acb, cab, cba]

方法：编写一个递归函数, 该函数将生成字符串的所有排列。终止条件为传递的字符串为空时, 在这种情况下该函数将返回一个空数组列表。在添加生成的字符串之前, 只需检查它是否已经生成即可获取不同的排列。

下面是上述方法的实现：

//Java implementation of the approach
import java.util.ArrayList;
  
public class GFG {
  
     //Function that returns true if string s
     //is present in the Arraylist
     static boolean isPresent(String s, ArrayList<String> Res)
     {
  
         //If present then return true
         for (String str : Res) {
  
             if (str.equals(s))
                 return true ;
         }
  
         //Not present
         return false ;
     }
  
     //Function to return an ArrayList containg
     //all the distinct permutations of the string
     static ArrayList<String> distinctPermute(String str)
     {
  
         //If string is empty
         if (str.length() == 0 ) {
  
             //Return an empty arraylist
             ArrayList<String> baseRes = new ArrayList<>();
             baseRes.add( "" );
             return baseRes;
         }
  
         //Take first character of str
         char ch = str.charAt( 0 );
  
         //Rest of the string after excluding
         //the first character
         String restStr = str.substring( 1 );
  
         //Recurvise call
         ArrayList<String> prevRes = distinctPermute(restStr);
  
         //Store the generated sequence into
         //the resultant Arraylist
         ArrayList<String> Res = new ArrayList<>();
         for (String s : prevRes) {
             for ( int i = 0 ; i <= s.length(); i++) {
                 String f = s.substring( 0 , i) + ch + s.substring(i);
  
                 //If the generated string is not
                 //already present in the Arraylist
                 if (!isPresent(f, Res))
  
                     //Add the generated string to the Arraylist
                     Res.add(f);
             }
         }
  
         //Return the resultant arraylist
         return Res;
     }
  
     //Driver code
     public static void main(String[] args)
     {
         String s = "abbb" ;
         System.out.println(distinctPermute(s));
     }
}

输出如下：