题解 | #查找兄弟单词#

/*
    输入：字典的容量 字典 x k
    输出: 字典中x的兄弟单词的数量 \n 第k个兄弟单词
*/

import java.util.*;
public class Main {
    public static void main(String[] args) {
        // 输入处理
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] tmp = line.trim().split(" ");
        int len = tmp.length;
        int dictC = Integer.parseInt(tmp[0]);
        String x = tmp[len - 2];
        int k = Integer.parseInt(tmp[len - 1]);
        // 创建字典（不可以用字典，字典可能有重复元素，但是兄弟字典可能也有多个）
        // 直接用List可以解决问题，但是时间消耗大，因此选用HashMap
        Map<String, Integer> dictMap = new HashMap<>();
        for (int i = 1; i < dictC + 1; i++) {
            dictMap.put(tmp[i], dictMap.getOrDefault(tmp[i], 0) + 1);
        }
        // 创建兄弟单词列表
        List<String> brotherList = generateBrotherList(x);
        List<String> brotherInDictList = new ArrayList<>();

        // 开始判断
        for (String brother : brotherList) {
            if (dictMap.containsKey(brother)) {
                for (int i = 0; i < dictMap.get(brother); i++) {
                    brotherInDictList.add(brother);
                }
            }
        }
        Collections.sort(brotherInDictList);
        int size = brotherInDictList.size();
        System.out.println(size);
        if (size >= k) {
            System.out.println(brotherInDictList.get(k - 1));
        }
    }

    public static List<String> generateBrotherList(String str) {
        char[] arrC = str.toCharArray();
        List<String> brotherList = new ArrayList<>();
        dfs(brotherList,arrC,0, arrC.length - 1);
        // brotherList删除本身str，还要删除重复元素
        // 但是，再dfs添加时加一个判断就不会有重复元素
        brotherList.remove(str);
        return brotherList;
    }

    /**
     * 全排列：
     *     先看第一个位置，将第一个位置依次和后面的位置交换；
     *     再第一次交换的基础上，再看第二个位置，第二个位置一次和后面交换；
     *     循环操作
     */
    public static void dfs(List<String> brothers, char[] arr, int start, int end) {
        if (start == end) {
            // 组成一个全排序
            // String brother = new String(arr);
            String brother = String.valueOf(arr);
            if (!brothers.contains(brother)) {
                brothers.add(brother);
            }
        }
        for (int i = start; i <= end; i++) {
            swap(arr, start, i);  // 当前第一个数start和后面所有的数交换
            dfs(brothers, arr,start + 1, end);
            swap(arr, i, start);  // 恢复，用于下一次交换
        }
    }

    public static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 }