查找固定长度的单词链

c9x0cxw0 于 2021-07-12 发布在 Java

关注(0)|答案(1)|浏览(361)

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

Java Dictionary depth-first-search breadth-first-search

来源：https://stackoverflow.com/questions/67222993/find-wordchain-of-a-fixed-length-java

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

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]

赞(0）回复(0）举报 2021-07-12

我来回答

查找固定长度的单词链

1条答案

假设

暴力-自顶向下递归

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

相关问题

热门标签

最新问答