查找固定长度的单词链

c9x0cxw0  于 2021-07-12  发布在  Java
关注(0)|答案(1)|浏览(355)

首先,对于那些不熟悉的人来说,词链问题是;当给定一本单词词典时,只需改变一个字母就可以找到从一个单词到另一个单词的路径。如。
给定词典 [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);
          }
        }
      }
    }
  }
9wbgstp7

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` 表示顶点

protected List<Integer> findPathWithLength(final int source, final int to, 
    final int pathLength, List<List<Integer>> graph, boolean[] visited, 
    List<Integer> path) {

    if (pathLength == 0 && source == to) {
        return path;
    } 
    if (pathLength < 0 || (pathLength == 0 && source != to)) {
        return false;
    }
    for (int adj : graph.getDirectlyConnectedVertices(current)) {
        if (visited[adj]) {
            continue;
        }
        visited[adj] = true;
        path.add(adj);
        List<Integer> result = findPathWithLength(adj, to, pathLength - 1, 
            graph, visited, path);
        if (result != null) {
            return result; // result and path are same in this code
        }
        visited[adj] = false;
        path.remove(path.length - 1);
    }
    return null;
}

使用顶点对和路径长度的记忆

对于每对顶点,尝试查找长度在[0,pathlength]范围内的边,并记住此结果
最后返回cachce[start][end][pathlength]

相关问题