题解 | #牛牛的字符串排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param k int整型
     * @return string字符串一维数组
     */
    public String[] getPermutation(String s, int k) {
        char[] chars = s.toCharArray(); // 将字符串转化为字符数组
        boolean[] used = new
        boolean[chars.length]; // 用于标记字符是否已经被使用过
        StringBuilder path = new StringBuilder(); // 用于保存当前的排列结果
        List<String> result = new ArrayList<>(); // 用于保存所有的排列结果
   Arrays.sort(chars);
        backtrack(chars, used, path, result, k); // 调用回溯函数
        String [] str = new String[result.size()];
        for (int i = 0; i < result.size(); i++) {
            str[i] = result.get(i);
        }
        return str; // 返回结果集
    }

    private void backtrack(char[] chars, boolean[] used, StringBuilder path,
                           List<String> result, int k) {
        if (result.size() == k) { // 如果已经生成了k个排列，直接返回
            return;
        }

        if (path.length() ==
                chars.length) { // 如果已经生成了一个完整的排列，添加到结果集中
            result.add(path.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) { // 遍历字符数组
            if (used[i]) { // 如果字符已经被使用过，跳过
                continue;
            }

            path.append(chars[i]); // 将当前字符添加到路径中
            used[i] = true; // 标记当前字符为已使用

            backtrack(chars, used, path, result,
                      k); // 递归调用回溯函数，生成下一个字符的排列

            path.deleteCharAt(path.length() -
                              1); // 回溯，将当前字符从路径中移除
            used[i] = false; // 标记当前字符为未使用
        }
    }
}

本题知识点分析：

1.回溯法

2.集合存取

3.数组遍历

本题解题思路分析：

1.先sort排序chars字符串

2.利用回溯法

3.1 如果已经生成了k个排列，直接返回

3.2 如果已经生成了一个完整的排列，添加到结果集中

3.3 如果字符已经被使用过，跳过

本题使用编程语言: Java