首先,对于那些不熟悉的人来说,词链问题是;当给定一本单词词典时,只需改变一个字母就可以找到从一个单词到另一个单词的路径。如。
给定词典 [dog, dot, cot, cat, cut, cab]
从狗到猫,一次换一个字母。路径是 dog > dot > cot > cat
通常使用单词链时,你会想使用bfs从dog->cat中找到最短路径,但是你会如何做一个固定长度的路径(例如,你得到了输入) dog cat 5
它要你从狗到猫分五步走。
新的道路将是 dog > dot > cot > cut > cat
使用普通的bfs来寻找最短路径将不再有效。
这是我当前的代码,它接收一个字典,存储它并计算字典中的每个单词“相邻单词”(一个字母变化)。
private static HashMap<String, ArrayList<String>> adjacentWords = new HashMap<>();
private static HashSet<String> dictionary = new HashSet<String>();
private static void initDictionary() {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
String word = input.nextLine();
dictionary.add(word);
adjacentWords.put(word, new ArrayList<String>());
}
input.close();
/**Checks each word in the dictionary one letter changes, if the word exists in dictionary,
* add it as an adjacent word
* /
for(String word: adjacentWords.keySet()){
for(int i=0;i<word.length();i++){
char[] words = word.toCharArray();
for(char c = 'a'; c<= 'z'; c++){
words[i]= c;
String oneLetterChange = String.valueOf(keys);
if(dictionary.contains(oneLetterChange)){
adjacentWords.get(words).add(oneLetterChange);
}
}
}
}
}
1条答案
按热度按时间9wbgstp71#
假设
顶点只能访问一次
暴力-自顶向下递归
让我们定义几个变量:
pathLength
是从源到目标的预期路径中所需的边数(如果存在这样的路径)graph
是邻接表示count
是顶点数。图中的每个顶点都有一个范围为[0,count]的id该算法可以是一种采用参数的方法
图表
计数
当前(当前顶点id)
到(目标顶点id)
路径长度(剩余路径长度)
路径(保存当前路径的结构)
该方法可以检查退出条件
pathLength < 0
是仅向前状态机中的无效状态,因此将返回null
pathLength == 0
以及current == to
,然后我们找到了一条路,所以返回path
pathLength == 0
以及current != to
,然后返回null
pathLength > 0 and
电流==至, then return
空实际通话将是 迭代所有未访问的边
current作记号
to访问时 添加
to到路径 使用调用方法
edge.to以及
pathLength - 1如果找到路径(非空响应),则返回路径 如果响应为空,则返回(标记为
unvisited和流行音乐
to从路径) 示例代码
Integer` 表示顶点使用顶点对和路径长度的记忆
对于每对顶点,尝试查找长度在[0,pathlength]范围内的边,并记住此结果
最后返回cachce[start][end][pathlength]