程序员经验分享-hwhale

编写拼字游戏的算法

2024-02-11

我正在研究一个类似填字游戏的问题，但我不知道如何设计算法。

例如：

  • 字典里有“汽车”、“苹果”等词。
  • 黑板上给出了“app”一词。
  • 有像 'l' 'e' 'c' 'r'... 这样的字母用于造词。

所以算法的任务是生成存储在字典中的正确单词。

app -> lapp -> leafp -> lecapp -> .... -> lappe -> eappc -> ... -> appl -> apple （正确答案）

该算法的最佳解决方案是什么？


您可能有兴趣在谷歌上搜索该研究论文“世界上最快的拼字游戏程序” http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf阿佩尔和雅各布森 (1988)。这些算法是用伪代码概述的，因此需要一些工作才能将其塑造成可用的形式并将其粘合在一起；然而，作者概述的程序效果很好。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

编写拼字游戏的算法 的相关文章

  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要

  • 将字符串中的“奇怪”字符转换为罗马字符

    我需要能够将用户输入仅转换为 a z 罗马字符 不区分大小写 所以 我感兴趣的角色只有26个 然而 用户可以输入他们想要的任何 形式 的字符 西班牙语 n 法语 e 和德语 u 都可以包含用户输入中的重音符号 这些重音符号会被程序删除 我已

  • 关于在字典中查找所有有效单词的算法问题

    给定一个字典 只是一个字符串列表 您收到来自外部来源的未知数量的信件 给定字母串 您将如何列出您可以通过这些字母的任意组合组成的所有有效单词 来自字典 因此 如果您收到 applead 你应该找到apple bad pad lead等 我知

  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i

  • C 埃及分数

    古埃及人仅使用以下形式的分数1 n因此任何其他分数都必须表示为这些单位分数的总和 而且 所有单位分数都是不同的 在C或Java中使任何分数成为埃及分数 总和越少越好 的好方法是什么 可以使用什么算法 分支定界 a 例如 3 4 1 2 1

  • 包围一组点的多边形

    我有一组 S 点 2D 由 x 和 y 定义 我想找到 P 包围该组所有点的最小 含义 具有最少数量的点 多边形 P 是S 有没有已知的算法来计算这个 我在这个领域缺乏文化令人惊讶 感谢您的帮助 对于这个问题有很多算法 它被称为 最小边界框

  • 带路径压缩算法的加权 Quick-Union

    有一种 带路径压缩的加权快速联合 算法 代码 public class WeightedQU private int id private int iz public WeightedQU int N id new int N iz new

  • 用 C++ 生成 AST

    我正在用 C 制作一个解释器 到目前为止我已经有了词法分析器来生成标记 问题是我不确定如何生成 行走 解析树 我正在考虑使用数组数组来制作解析树 但我不确定如何以正确的顺序将标记实际插入到解析树中 我不确定是自上而下 左右还是自下而上 左右

  • 使用多级解决方案计算二维网格中的最近邻

    我有一个问题 在 x y 大小的网格中 我提供了一个点 并且我需要找到最近的邻居 在实践中 我试图在 pygame 中找到距离光标最近的点 该点跨越颜色距离阈值 计算如下 sqrt rgb1 0 rgb2 0 2 rgb1 1 rgb2 1

  • C# 中的 strstr() 等效项

    我有两个byte 我想找到第二个的第一次出现byte 在第一个byte 或其中的一个范围 我不想使用字符串来提高效率 翻译第一个byte to a string会效率低下 基本上我相信就是这样strstr 在 C 中做 最好的方法是什么 这

  • 数学组合的完美最小哈希

    首先定义两个整数N and K where N gt K 两者都在编译时已知 例如 N 8 and K 3 接下来 定义一组整数 0 N or 1 N 如果这使答案更简单 并调用它S 例如 0 1 2 3 4 5 6 7 的子集数量S wi

  • 计算两点之间的最短路线

    过去几周我一直在开发一款多人 HTML5 游戏 使用nodejs and websockets 我已经被这个问题困扰了一段时间 想象一下 我用数组实现了这个平铺地图 如下所示 1 or 棕色瓷砖 路上有障碍物 玩家无法通过 0 or 绿色瓷

  • 具有多个谓词的 C++11 算法

    功能如std find if来自algorithmheader 确实很有用 但对我来说 一个严重的限制是我只能为每次调用使用 1 个谓词count if 例如给定一个像这样的容器std vector我想同时应用相同的迭代find if 多个

  • shell脚本中关联数组的时间复杂度

    我想知道在 shell 脚本中使用关联数组时如何构造 实现 另外 我想知道基于 shell 脚本的关联数组的时间复杂度是否是最佳的 因为我们可以使用字母和数字作为它们各自的键 编辑 他们使用什么哈希函数 如果您使用关联数组 则不能通过 使用

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • 在 O(n) 时间内排序？

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an

  • Java递归方法求阶乘返回负输出[重复]

    这个问题在这里已经有答案了 我知道这是溢出 但问题是 20 是相对较小的数字 这不应该发生 对吧 有没有更好的方法来查找大数 例如 1000 的阶乘 而不会得到这种奇怪的结果 public class RecursiveFunctionsE

  • 以 O(1) 计算汉明权重 [重复]

    这个问题在这里已经有答案了 在二进制表示中 汉明权重是 1 的数量 我偶然发现了网络并找到了一个 O 1 的答案 v v v gt gt 1 0x55555555 v v 0x33333333 v gt gt 2 0x33333333 in

  • 解开 Knuth 的结：如何重构意大利面条式代码？

    这个问题的灵感来自如何将流程图转化为实施 https stackoverflow com questions 36647765它询问如何通过算法消除goto代码中的语句 这answer https stackoverflow com a 3

  • 数量重新分配逻辑 - 具有外部数据集的 MapGroups

    我正在研究一种复杂的逻辑 需要将数量从一个数据集重新分配到另一个数据集 在例子中我们有Owner and Invoice 我们需要从数量中减去Invoice准确地Owner匹配 在给定汽车的给定邮政编码处 减去的数量需要重新分配回同一辆车出

随机推荐

热门标签