求解波格的函数的最佳时间复杂度O（n）是多少，其中博格板是n乘n？
我觉得这很n^2因为对于每个角色，我们必须查看其他角色2(n-1)。面试官认为，查找O(1)字典并不n^2。
目前还不清楚字典的功能。
有点傻，但在我看来正确答案如下：
由于在 boggle 中，单词可以任意方式（从每个字符到该单词中尚未使用的任何相邻（水平、垂直或对角线）字符），对于长度为 L 的单词，单词的组成最多可以达到 8^L，除非您消除字符多次出现的组合。无论如何，考虑到L是常量（因为使用的字典是常量），这个值也是常量。综上所述，从给定位置开始查找单词的时间复杂度为 O(1) 。
所以剩下的是单词的起始位置，它在空间n^2，所以你的博格求解器的时间复杂度O(n^2)，你是对的。
如前所述，我认为这种论点有点愚蠢。
问题可能是人们不想认为字典是恒定的，因为它非常大。假设它是无限大的，但它实现了对现有单词的O(1)查找（这是我们可用于字典的唯一查询，特别是没有对单词前缀的查找），并进一步假设n不是与单词长度相比的限制因素，时间复杂度是指数级的。但我认为，在此练习中，仅对现有单词进行查找成功的假设是错误的。
另一个可能的假设是，字典有一个单词前缀的查找（它返回是否存在以给定字符串开头但不一定等于字符串的单词）。在这种情况下，我们可以实现一个更好、更复杂的算法来搜索有限的搜索空间（每个字符最多使用一次）。字长的一个限制因素是 n^2 ，因为没有一个字（包含在当前的 boggle board 中）可以比这更长（因为我们每个字符只能使用一次）。同样，起始位置在空间n^2，所以一个愚蠢的基于路径的算法的时间复杂度会O(n^4)，所以你错了。目前，我想不出在这个假设下具有更好时间复杂度的算法。
看看 http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html。 动态规划解决方案是 O（D），其中 D 是字典的大小。
我终于想通了。答案在时间上是指数级的。
想象一个 4X4 的笨拙网格
ABCD
EFGH
IJKL
MNOP
例如，ABCDHGFEIJKLPONM 中任何以 A 开头的有序子序列都是一个潜在的词;AEIMNOPLHDCBFJKG 或 AEIMNOPLHGFIK 或 ABCDHLPONMIEFGKJ 中任何以 A 开头的有序子序列也是如此。然后我们需要查看以 B 开头的潜在单词，然后以 C 开头，依此类推。
让我们换个角度来看这个问题。假设我们只需要考虑_ABCD，其中_代表一些起始角色，比如X;那么属于幂集的潜在词是：
XD; XC; XCD; XB; XBD; etc.
因此，仅考虑从每个字符开始的顺时针螺旋，我们已经在看 n^2*2^(n-1) . n^2因为网格是n by n的，所以对于4 by 4网格，有 16 个可能的起始字符。2^(n-1)因为每个起始角色领导的力量。当然，顺时针螺旋并不是唯一可能的模式。但是我们已经可以看到第一种模式的时间复杂度：Big-Omega（2^n），它是指数级的。