草庐IT

javascript - 两个 Trie 节点之间的最短路径

coder 2023-08-21 原文

这是一个双重问题，因为我不知道如何最有效地实现它。

我有一个包含 150,000 个单词的字典，存储在一个 Trie 实现中，这是我的特定实现的样子:

用户被提供了两个词。目标是找到其他英语单词(每个改变一个字符)从起始单词到结束单词的最短路径。

例如:

Start: Dog

End: Cat

Path: Dog, Dot, Cot, Cat

Path: Dog, Cog, Log, Bog, Bot, Cot, Cat

Path: Dog, Doe, Joe, Joy, Jot, Cot, Cat

我目前的实现已经经历了几次迭代，但我可以提供最简单的伪代码(因为实际代码是几个文件):

var start = "dog";
var end = "cat";
var alphabet = [a, b, c, d, e .... y, z];
var possible_words = [];

for (var letter_of_word = 0; letter_of_word < start.length; letter_of_word++) {
  for (var letter_of_alphabet = 0; letter_of_alphabet < alphabet.length; letter_of_alphabet++) {
      var new_word = start;
      new_word.characterAt(letter_of_word) = alphabet[letter_of_alphabet];
      if (in_dictionary(new_word)) {
          add_to.possible_words;
      }
  }  
}

function bfs() {
    var q = [];
    ... usual bfs implementation here ..
}

已知:

  • 一个开始词和一个结束词
  • 单词长度相同
  • 单词是英文单词
  • 有可能没有路径

问题:

我的问题是，我没有一种有效的方法来确定要尝试的潜在单词，而无需暴力破解字母表并根据字典检查每个新单词。我知道有一种使用前缀的更有效方式的可能性，但我想不出一个合适的实现，或者一个不只是加倍处理的实现。

其次，我是否应该使用不同的搜索算法，我已经将 A* 和最佳优先搜索视为可能，但它们需要权重，而我没有。

想法？

最佳答案

按照评论中的要求，通过在整数位中编码链接词来说明我的意思。

在 C++ 中，它可能看起来像...

// populate a list of known words (or read from file etc)...
std::vector<std::string> words = {
    "dog", "dot", "cot", "cat", "log", "bog"
};

// create sets of one-letter-apart words...
std::unordered_map<std::string, int32_t> links;
for (auto& word : words)
    for (int i = 0; i < word.size(); ++i)
    {
        char save = word[i];
        word[i] = '_';
        links[word] |= 1 << (save - 'a');
        word[i] = save;
    }

以上代码运行后，links[x] - 其中x是一个单词，其中一个字母被下划线替换为la d_g - 检索一个整数，指示可以替换下划线以形成已知单词的字母。如果最低有效位打开，则“dag”是一个已知单词，如果从最低有效位开始的下一个打开，则“dbg”是已知单词等。

直觉上我希望使用整数来减少用于链接数据的整体内存，但如果大多数单词每个只有几个链接单词，存储一些索引或指向这些单词的指针实际上可能使用更少的内存 - 而且是如果您不习惯按位操作，则更容易，即:

std::unordered_map<std::string, std::vector<const char*>> links;
for (auto& word : words)
    for (int i = 0; i < word.size(); ++i)
    {
        char save = word[i];
        word[i] = '_';
        links[word].push_back(word.c_str());
        word[i] = save;
    }

无论哪种方式，您都会得到一个图表，将每个单词链接到它可以通过单个字符更改转换成的单词。然后您可以应用 Dijkstra's algorithm 的逻辑找到任意两个单词之间的最短路径。

关于javascript - 两个 Trie 节点之间的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34012573/

javascriptTrie单词wordcodepythonalgorithmperformancesorting

有关javascript - 两个 Trie 节点之间的最短路径的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  3. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  4. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  5. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  6. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  7. [工业相机] 分辨率、精度和公差之间的关系 - 2

    📢博客主页：https://blog.csdn.net/weixin_43197380📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由Loewen丶原创，首发于CSDN，转载注明出处🙉📢现在的付出，都会是一种沉淀，只为让你成为更好的人✨文章预览：一.分辨率（Resolution）1、工业相机的分辨率是如何定义的？2、工业相机的分辨率是如何选择的？二.精度（Accuracy）1、像素精度（PixelAccuracy）2、定位精度和重复定位精度（RepeatPrecision）三.公差（Tolerance）四.课后作业（Post-ClassExercises）视觉行业的初学者，甚至是做了1~2年

  8. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  9. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  10. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

随机推荐