今天小弟问了我一个问题，问题如下：
Given a list of strings & string M28K, where M28K represents a string which starts
from M, ends with K and has 28chars in between . Find if M28K is unique in the
list of strings or not?
我想出了以下算法来找到问题的解决方案：
对于每个字符串：
find string length(L)
if(L==30) then
if(str[0]=='M' && str[L-1]=='K') then
verify rest of 28 characters are matching or not
就时间复杂度而言，该解决方案似乎效率不高。谁能给出更好的算法来解决这个问题？
我会去散列。通常，由于这听起来像是一个算法作业问题，以我的经验，我们不允许用散列来回答，因为它真的取决于你的散列函数。如果它不够好，那么您将不会获得每个字符串的唯一值。
我会根据字符串中的字符将字符串列表构建成二叉排序树。维护一个算法，如果字符串按字母顺序位于头节点之前，则将其放在左侧，如果在头节点之后，则将其放在右侧。当然是递归的。我们有一棵树。现在授予最坏的情况，这将在 O(n) 时间内完成，这实际上只是一个链表，但是在 m 或 n 区域的某个地方有一个好的头节点，这个查找可以在 O(log n) 内完成. 所以整个操作需要 O(n log n) 时间。
您提供的算法，最坏的情况将需要 O(n^2)。假设每个字符串有 30 个字符，并以 K 结尾并以 L 开头。除倒数第二个字符外。实际上，我们将搜索所有提供的字符串的 28 个字符。n^2 用于查找所有字符串的大小。每个字符串都需要 O(n) 时间，使其成为 n^2 算法。在我的算法中，我们每次都将问题减半，这提供了更快的搜索速度。