您有以下网格。
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
光标始终从 A 开始，并且可以进行左 (L)、右 (R)、上 (U)、下 (D) 和 Enter (E) 操作。 问题:给定一个字符串，打印生成该字符串的操作序列？
例如:
> INPUT : CGH
> OUTPUT : R R E D E R E
这个问题是我在面试时被问到的。
我的方法:我想通过计算曼哈顿距离并在图上进行 BFS 来解决这个问题，但我认为这不是最佳的。甚至我需要改变每个字母的曼哈顿距离。
提前致谢
最佳答案
人们可以从天真的方法开始。提示:将初始序列视为矩阵，每个字母都有一个位置:行和列的索引。
第 1 步。
构建一个哈希表:键 - 是字母，值 - 是二维矩阵中的索引。您可以使用它来快速查找，例如给定字母“C”，它的矩阵索引是多少？是[0,2]。
构建需要 O(N) 时间和 O(N) 空间，因为您需要迭代输入并存储它。在平均情况下，解析一个字母需要 O(1) + 如果您使用良好的哈希函数，最坏情况下的 O(N) 不会成为问题。
第 2 步。
给定输入中的 2 个字母即可解析偏移量。这将为您提供所需的输出序列 block 。
这需要 O(1) 时间和 O(1) 空间。
第 3 步。
重复步骤 2，直到到达序列末尾。
这需要 O(N) 时间和 O(N) 空间来构建输出。
摘要。
该解决方案使用哈希表来快速查找字母。解析路径的偏移量(L/R/U/D/E)也需要 O(N) 时间复杂度和 O(N) 空间复杂度。
关于algorithm - 通过遍历图生成给定字符串的步骤，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12239310/