Java实现字符串全排列无重复解决方案

5星 · 超过95%的资源 | 下载需积分: 42 | TXT格式 | 8KB | 更新于2024-09-10 | 124 浏览量 | 举报

1 收藏

"Java_字符串全排列大全_(已解决重复问题)：这是一个Java程序，用于生成给定字符串的所有可能的全排列，并且已经解决了在排列过程中可能出现的重复问题。程序通过深度优先搜索（DFS）或回溯算法实现，确保生成所有不重复的排列组合。" 在Java编程中，字符串的全排列是一个常见的问题，特别是在处理数据和算法题目时。全排列是指将一个字符串中的所有字符进行所有可能的排列组合。给定的代码提供了两种不同的方法来解决这个问题： 1. **基于DFS的解决方案**： - 这个方法使用了深度优先搜索策略。首先定义一个静态变量`count`来记录有效排列的数量。 - `main`函数接收用户输入的字符串`s`，然后调用`Pailie`函数开始排列过程。 - `Pailie`函数是递归的核心，当字符串长度小于1时，表示当前排列已完成，打印排列并增加计数。 - 在递归过程中，使用一个整型数组`index`存储每个字符在原始字符串中的位置，避免重复排列。通过遍历和交换字符，确保每次选择未出现过的字符。 2. **基于回溯的解决方案**： - 第二种方法利用了回溯算法，使用`LinkedList`存储中间结果。创建一个类`ALL`，包含输入字符串和一个方法`insert`。 - `insert`方法接受一个字符列表和一个待插入的字符，遍历列表并将字符插入到所有可能的位置，同时返回新的列表集合，用于继续回溯。这两种方法都能有效地生成字符串的全排列，但它们的实现方式有所不同。DFS方法直接操作字符串，而回溯方法则使用链表结构来辅助排列。两种方法都避免了重复的排列，确保了所有生成的排列都是唯一的。在实际应用中，处理字符串的全排列问题可以应用于很多场景，例如密码生成、数据分析、组合优化等。理解并能熟练运用这些算法对于提升Java程序员的算法能力和解决问题的效率至关重要。

展开

//字符串全排列问题 (解决了重复问题)
import java.util.*;
public class ListALL {
static int count=0;
public static void main(String[] arg) {
Scanner r=new Scanner(System.in);
String s=r.nextLine();
Pailie(s, " ");
System.out.println("共有 "+count+"种情况");
}
static void Pailie(String s,String p) {
if(s.length()<1) {
System.out.println(p);//字符串长度小于1，换行
count++;
}
else{
int index[]=new int[s.length()];
for(int i=0;i<s.length();i++)
//该循环将所有字符的第一次出现的位置记录在数组index中
index[i]=s.indexOf(s.charAt(i));
for(int i=0;i<s.length();i++){
if(i==index[i])
//只有当循环数与第一次记录数相等时才递归，保证相同字符中的第一个调用
Pailie(s.substring(1),p+s.substring(0,1));//递归，打印其它字符
s=s.substring(1)+s.substring(0,1);//循环移位
}
}
}
}