小学生都能看懂的题解 | #字符串的排列#

字符串的排列

https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

问题描述：

给定一个字符串，我们需要找出这个字符串中所有可能的排列组合。例如，如果输入字符串是 "abc"，那么输出应该是 ["abc", "acb", "bac", "bca", "cba", "cab"]。

解决方案：

想象一下，我们有一盒彩色的小球，每个小球代表一个字符。我们的任务是把这些小球按不同的顺序排列出来。如果小球的颜色相同，那么相同的颜色不能出现在同一个排列中两次。

具体步骤如下：

如果盒子里没有小球，那么只有一个排列，就是空排列。
如果盒子里只有一个小球，那么也只有一个排列。
如果盒子里有两个小球，我们可以交换这两个小球得到两个不同的排列。
如果盒子里有三个或更多小球，我们可以固定一个小球在最前面的位置，然后对剩下的小球进行全排列。重复这个过程，直到每个小球都有机会排在最前面。

为了保证不重复，我们可以记录已经排好的顺序，如果某个顺序已经排过了，就不重复排。

代码实现：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class StringPermutations {

    /**
     * 获取字符串的所有排列组合（去重）
     * @param str 输入的字符串
     * @return 字符串的所有排列组合
     */
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> results = new ArrayList<>();
        
        // 如果字符串为空，只有一个排列就是空字符串
        if (str == null || str.length() == 0) {
            results.add("");
            return results;
        }
        
        // 使用HashSet来去重
        Set<String> uniquePermutations = new HashSet<>();
        
        // 对于每个字符，都尝试将其放在第一位，并对剩下的字符进行排列
        for (int i = 0; i < str.length(); i++) {
            // 当前字符
            char firstChar = str.charAt(i);
            
            // 去掉当前字符后的剩余字符串
            String rest = str.substring(0, i) + str.substring(i + 1);
            
            // 获取剩余字符串的所有排列
            ArrayList<String> restPermutations = Permutation(rest);
            
            // 把当前字符加到剩余字符串的每个排列前面，并添加到HashSet中去重
            for (String permutation : restPermutations) {
                String newPermutation = firstChar + permutation;
                uniquePermutations.add(newPermutation);
            }
        }
        
        // 将HashSet中的排列转换为ArrayList
        results.addAll(uniquePermutations);
        
        return results;
    }

    
}

解释：

初始化结果列表：我们创建一个 ArrayList 来存储所有的排列。
处理空字符串：如果输入的字符串为空或长度为0，那么只有一个排列就是空字符串。
使用HashSet去重：在递归生成排列的过程中，使用 HashSet 来存储已经生成的排列，确保不会有重复。
递归排列：对于每个字符，我们把它放在第一位，然后递归地对剩下的字符串进行全排列。每次递归完成后，我们将当前字符加到每个排列前面，并添加到 HashSet 中去重。
转换为ArrayList：最后将 HashSet 中的排列转换为 ArrayList 并返回。