algorithm - 查找特定位置不变的字符串的所有排列

Question

给定一串单词，说“OhMy”，保持大写字母固定(不变)，但我们可以改变小写字母的位置。输出所有可能的排列。

例如。给定“OhMy”它应该输出[“OhMy”，“OyMh”]

这是我做的:

    public static List<String> Permutation(String s){
    List<String> res = new ArrayList<String>();
    if (s == null || s.length() == 0){
        return res;
    }
    StringBuilder path = new StringBuilder(s);
    List<Character> candidates = new ArrayList<Character>();
    List<Integer> position = new ArrayList<Integer>();
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (Character.isAlphabetic(c) && Character.isLowerCase(c)){
            candidates.add(c);
            position.add(i);
        }
    }
    boolean[] occurred = new boolean[candidates.size()];
    helper(res, path, candidates, position, 0);
    return res;
}

public static void helper(List<String> res, StringBuilder path, List<Character> candidates, List<Integer> position, int index){
    if (index == position.size()){
        res.add(path.toString());
        return ;
    }
    for (int i = index; i < position.size(); i++){
        for (int j = 0; j < candidates.size(); j++){
            path.setCharAt(position.get(i), candidates.get(j));
            char c = candidates.remove(j);
            helper(res, path, candidates, position, index+1);
            candidates.add(j, c);
        }
    }
}

用于输入“Abc” 它将有结果 [Abc, Acb, Acc, Acb] 本质上，外循环迭代每个可能的位置，内循环在每个可能的位置尝试每个可能的候选者。 我不知道为什么它有重复的 li "Acc, Acb"

Answer 1

您隐含问题的重点似乎是如何有效地枚举给定集合的所有排列，您可以在线阅读(有几种方法)。如果您可以枚举小写字母索引的所有排列，那么做簿记并将小写字母的每个排列与原始不变的大写字母集合合并非常简单，尊重大写字母的位置，所以你可以输出你的字符串。如果您在这部分遇到困难，请更新您的问题，有人应该能够帮助您。