python - 是否可以在不使用性能优于 O(n^2) 的 sorted() 或字典的情况下检查字谜？

Question

我目前正在学习，有人告诉我不要使用“神奇”的 Python 技巧，例如 sorted() 或 Python 中的字符串拆分。

我误以为这只是使用数组来检查输入字符串是否为变位词。因此，虽然我首先想到的是使用字典，但我并没有追求它，因为我认为它是被禁止的。使用字典，我可以通过使用字母作为键并将计数作为值并向下计数(减去)输入字符串中遇到的字母频率并为频率字典做一个循环来查看字母的频率如果有任何零。

所以...由于对我设置的限制有错误的认识，我创建了一个如下所示的嵌套循环(问题假定长度相等，没有空格)

def anagram(original, input):
    for a in original:
        i=0
        for b in input:
            if a == b:
               del input[i]
            else:
               pass
        i+=1
    if len(input) == 0:
        return True
    else:
        return False

显然这是不可取的，因为大 o 符号是 O(n^2) 到使用字典的解决方案，这将是 O(3n)，两次迭代计算频率，最后一次迭代检查是否有任何条目字典有一个非零频率(这意味着这不是一个字谜)。

所以这是我这边的一些理解问题，但我没有继续前进，而是想自己是否有可能在不使用字典和仅依赖在数组/列表上？

我有另一个想法但我停止了:

1) 将字符串字符列表转换为数字列表 - 但这意味着我仍需要遍历引用字符(原始)以找到数字位置。

它一直在吞噬着我，我意识到我对这些简单的算法问题想得太多了......但仍然很好奇是否有满足标准的解决方案。

Answer 1

回答这个问题的 Pythonic 方式是使用 collections.Counter 对象:

from collections import Counter

def anagram(s1, s2):
    return Counter(s1) == Counter(s2)

但由于这些受到限制，您可以回退到 Vanilla 字典(也称为 HashMap ，这是许多高效算法的基本组成部分)。

---

高级流程如下。首先，为 string1 构建一个计数 HashMap 。对 string2 重复该过程。最后，比较两个 hashmap 是否相等。

首先是辅助函数——

def build_counts(string):
    ctr = {}
    for c in string:
        ctr[c] = ctr.setdefault(c, 0) + 1

    return ctr

现在，司机 -

def anagram(string1, string2):  
    c1 = build_counts(string1)
    c2 = build_counts(string2)

    return c1 == c2

复杂性分析 - 构建每个 hashmap 需要 O(N) 时间，执行比较也是 O(N)，因为你必须，一，测试键是否相同，二，比较相应键的值.总而言之，一个线性算法。

---

由于散列图和散列集是如此普遍，您不应争辩说这是受限的，除非您计划使用数组和开放寻址实现您自己的散列图。

不，没有不依赖 HashMap 或更复杂的东西的有效算法。除非您采用 viraptor 的答案，它基本上是散列映射的数组版本 (!)，但对 ASCII 集中的每个 字符都有一个唯一的条目。例如，ASCII 字符 65 的计数将通过 arr[65] 访问，等等。因此，您需要有一个足够大的数组来容纳每个 ASCII 字符。

仅 ASCII 字母的事情是可以管理的，但是当您考虑其他更广泛的编码 (unicode) 时，情节就变得复杂了。最后，只使用散列图会更节省空间。