题解 | #牛群排列#【Java】

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串一维数组
     */
    public String[] cowPermutations (String s) {
        ArrayList<String> arrayList = new ArrayList<>();
        StringBuilder tempStr = new StringBuilder();
        boolean [] isSelected = new boolean[s.length()];
        String[] split = s.split("");
        Arrays.sort(split);
        String s1 = String.join("", split);
        backTrack(arrayList,tempStr,s1,isSelected);
        String [] result = new String[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            result[i] = arrayList.get(i);
        }
        return result;
    }
    public void backTrack(ArrayList<String> resultList,StringBuilder tempStr,String s,boolean [] isSelected){
        if(tempStr.length()==s.length()){
            resultList.add(tempStr.toString());
        }
        for (int i = 0; i < s.length(); i++) {
            if(!isSelected[i]){
                tempStr.append(s.charAt(i));
                isSelected[i] = true;
                backTrack(resultList,tempStr,s,isSelected);
                isSelected[i] = false;
                tempStr.deleteCharAt(tempStr.length()-1);
            }
        }
    }
}

本题知识点分析：

1.递归

2.回溯

3.字符串

4.数学模拟

5.字典序排序

本题解题思路分析：

1.先对字符串进行排序，先将字符串的字符分割出来，调用Arrays.sort，然后再用join方法拼接成字符串，然后传入形参

2.利用递归+回溯，如果临时字符串的长度和目标字符串的长度相等，那么就添加到结果集合中

3.遍历s字符串，如果该元素未被选择过，那么添加到临时字符串，然后标记为true,然后递归到下一层，递归出来后，重置标记为false,然后移除字符串的最后一个元素，回溯

4.集合转一维数组返回

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~