题解 | #查找兄弟单词#
题目的理解：
输入：字典容量 字典元素... x k
输出：字典中是x的兄弟单词的数量 \n 第k个兄弟单词
思路：
1.依据x创建x的兄弟单词列表（全排列）
注意：
1）删除x自身；
2）此外，x中有重复char时产生的全排列有重复，因此add之前需要排除已有的情况；
2.字典处理的时候，可以用List，还可以用Map，List会有很多重复的情况，Map可以节省时空复杂度
1）注意，绝对不可以用set，因为字典里面也有重复的情况，如果重复的恰好是x的兄弟单词，则最后size的时候会漏记；
此外，还有一种设想，字典进行处理后，直接判断HashMap的key和x的关系：
1）长度至少需要相等
2）每个字符的数量一样
3）不能完全相等
/*
输入：字典的容量 字典 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;
}
}
