题目描述
小王设计了一个简单的猜字谜游戏，游戏的谜面是一个或多个错误的单词（如"nesw"），玩家需要猜出谜底库中正确的单词。猜中的要求如下：
- 变换顺序：谜面和谜底单词变换顺序后相同，例如"nwes"和"news"。
- 字母去重：谜面和谜底单词去重后的字母序列相同，例如"woo od"和"wo od"，去重后都是"w od"。
玩家需要在谜底库中找到所有满足上述任一条件的单词，并返回结果列表。如果找不到对应的谜底，则返回"not found"或类似信息。
输入描述
- 谜面单词列表，以","分隔。
- 谜底库单词列表，以","分隔。
输出描述
- 匹配到的正确单词列表，以","分隔。
- 如果找不到对应谜底，返回"not found"。
解题思路
-
读取输入：首先，从输入中读取谜面单词列表和谜底库单词列表，可以使用字符串分割函数（如Java中的
split）来将逗号分隔的字符串转换为列表。 -
遍历谜面单词：对于谜面中的每一个单词，执行以下步骤：
- 遍历谜底库中的每一个单词。
- 判断当前谜面单词和谜底单词是否满足变换顺序相同的条件（可以通过比较两个单词排序后的结果是否相同来实现）。
- 如果不满足变换顺序条件，则判断去重后的字母序列是否相同（可以将两个单词转换为集合后比较）。
- 如果满足任一条件，则将该谜底单词添加到结果列表中，并跳出内层循环（因为已经找到匹配的谜底，无需继续检查其他谜底）。
-
处理结果：如果对于某个谜面单词，在谜底库中没有找到匹配的单词，则将"not found"添加到结果列表中（注意，根据题目要求，这可能是在所有谜面单词处理完毕后统一判断，也可能是在处理单个谜面单词时即时判断，具体取决于题目要求和编程习惯）。
-
输出结果：最后，将结果列表中的单词以逗号分隔的形式输出。
示例
假设输入如下：
谜面: conection,today
谜底库: connection,wrong,today
输出应为：
connection,today
注意事项
- 确保处理字符串时考虑到大小写敏感性（根据题目描述，本例中只涉及小写英文字母）。
- 考虑到性能问题，如果谜底库非常大，可能需要优化算法以减少不必要的比较。但在大多数情况下，由于单词数量和词汇表数量的限制（如0<N<1000, 0<M<1000），简单的双重循环遍历即可满足要求。
- 注意处理边界情况，如谜面或谜底库为空的情况。
代码实现
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class WordPuzzleGame {
private static final Logger log = LoggerFactory.getLogger(WordPuzzleGame.class);
public static void main(String[] args) {
// 示例输入，实际情况下可以从文件、控制台或其他输入源读取
String clues = "conection,today";
String answers = "connection,wrong,today";
// 调用函数处理输入并输出结果
List<String> results = solvePuzzle(clues, answers);
// 输出结果
if (results.isEmpty()) {
System.out.println("not found");
} else {
System.out.println(String.join(",", results));
}
}
/**
* 解决谜语谜底匹配问题
*
* @param clues 谜语线索，多个线索用逗号分隔
* @param answers 谜底候选，多个谜底用逗号分隔
* @return 与线索匹配的谜底列表如果没有找到任何匹配，则返回包含"not found"的单元素列表
* *
* 该方法通过将线索和谜底字符串分割成数组，然后检查每条线索与每个谜底是否构成排列或字谜（anagram）
* 如果找到匹配的谜底，则添加到结果列表中如果未找到任何匹配的谜底，则返回包含"not found"的单元素列表
*/
public static List<String> solvePuzzle(String clues, String answers) {
// 将线索字符串分割成数组
String[] clueList = clues.split(",");
// 记录调试信息，显示分割后的线索数组
log.debug("谜面:{}", (Object) clueList);
// 将谜底字符串分割成数组
String[] answerList = answers.split(",");
// 记录调试信息，显示分割后的谜底数组
log.debug("谜底数组:{}", (Object) answerList);
// 创建一个列表，用于存储匹配的谜底
List<String> results = new ArrayList<>();
// 遍历线索数组
for (String clue : clueList) {
// 创建一个临时列表，用于存储当前线索匹配到的谜底
List<String> matches= new ArrayList<>();
// 遍历谜底数组
for (String answer : answerList) {
// 如果当前谜底与线索构成排列或字谜
if (isPermutation(clue, answer) || isAnagram(clue, answer)) {
// 将匹配的谜底添加到临时列表
matches.add(answer);
}
}
// 如果临时列表不为空
if (!matches.isEmpty()) {
// 将临时列表中的谜底添加到结果列表
results.addAll(matches);
}
}
// 如果结果列表为空，表示没有找到任何匹配的谜底
if (results.isEmpty()) {
// 返回包含"not found"的单元素列表
return Collections.singletonList("not found");
}
// 返回结果列表
return results;
}
/**
* 检查两个字符串是否是彼此的排列（即字符组成相同，但顺序可能不同）
*
* @param s1 第一个字符串
* @param s2 第二个字符串
* @return 如果两个字符串是彼此的排列，则返回true；否则返回false
*/
private static boolean isPermutation(String s1, String s2) {
// 打印调试信息，展示输入的两个字符串
log.debug("s1:{},s2:{}", s1, s2);
log.debug("------------");
// 如果两个字符串的长度不相等，它们不可能是彼此的排列，直接返回false
if (s1.length() != s2.length()) return false;
// 将两个字符串转换为字符数组
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
// 打印调试信息，展示转换后的字符数组
log.debug("arr1:{},arr1:{}", arr1, arr2);
// 判断两个字符数组是否相等，如果相等，则表示两个字符串是彼此的排列
boolean isPermutated = Arrays.equals(arr1, arr2);
// 打印调试信息，展示是否是彼此的排列
log.debug("是否是彼此的排列:{}", isPermutated);
log.debug("------------");
// 返回判断结果
return isPermutated;
}
/**
* 检查两个字符串是否是彼此的变位词（去重后字母序列相同）
* 变位词是指两个字符串在忽略空格和大小写的情况下，包含的字母种类和频率相同
*
* @param s1 第一个字符串
* @param s2 第二个字符串
* @return 如果两个字符串是变位词，则返回true；否则返回false
*/
private static boolean isAnagram(String s1, String s2) {
// 使用HashSet存储两个字符串中的字符，自动去重
HashSet<Character> set1 = new HashSet<>();
HashSet<Character> set2 = new HashSet<>();
// 遍历s1的字符，添加到set1中
for (char c : s1.toCharArray()) set1.add(c);
// 遍历s2的字符，添加到set2中
for (char c : s2.toCharArray()) set2.add(c);
// 日志输出两个字符串去重后的字符集合
log.debug("s1:{}----s2:{}", set1, set2);
log.debug("-------------");
// 判断两个字符集合是否相等，相等则表示两个字符串是变位词
log.debug("否是彼此的变位词:{}", set1.equals(set2));
return set1.equals(set2);
}
}
***运行解析***
1、分割输入字符串：
-
clues 分割为 [“conection”, “today”]。
-
answers 分割为 [“connection”, “wrong”, “today”]。
2、遍历线索并检查匹配：
- 对于线索 “conection”：
- 检查 “connection” 是否与其构成排列或变位词。
- isPermutation(“conection”, “connection”) 返回 false。
- isAnagram(“conection”, “connection”) 返回 true。
- 结果：“connection” 匹配。
- 检查 “wrong” 是否与其构成排列或变位词。
- isPermutation(“conection”, “wrong”) 返回 false。
- isAnagram(“conection”, “wrong”) 返回 false。
- 结果：不匹配。
- 检查 “today” 是否与其构成排列或变位词。
- isPermutation(“conection”, “today”) 返回 false。
- isAnagram(“conection”, “today”) 返回 false。
- 结果：不匹配。
- 检查 “connection” 是否与其构成排列或变位词。
- 对于线索 “today”：
-
检查 “connection” 是否与其构成排列或变位词。
- isPermutation(“today”, “connection”) 返回 false。
- isAnagram(“today”, “connection”) 返回 false。
- 结果：不匹配。
-
检查 “wrong” 是否与其构成排列或变位词。
- isPermutation(“today”, “wrong”) 返回 false。
- isAnagram(“today”, “wrong”) 返回 false。
- 结果：不匹配。
-
检查 “today” 是否与其构成排列或变位词。
- isPermutation(“today”, “today”) 返回 true。
- isAnagram(“today”, “today”) 返回 true。
- 结果：“today” 匹配。
-
3.最终结果：
- 匹配的谜底为 [“connection”, “today”]。
输出结果
根据上述解析，最终结果为：
connection,today