实施算法以确定字符串是否具有所有唯一字符

Question

上下文：我是CS
n00b，正在通过“破解编码面试”来完成自己的工作。第一个问题要求“实施一种算法以确定字符串是否具有所有唯一字符”。我的（可能是幼稚的）实现如下：

def isUniqueChars2(string):
  uchars = []
  for c in string:
    if c in uchars:
      return False
    else:
      uchars.append(c)
  return True

作者建议以下实现：

def isUniqueChars(string):
  checker = 0
  for c in string:
    val = ord(c) - ord('a')
    if (checker & (1 << val) > 0):
      return False
    else:
      checker |= (1 << val)
  return True

是什么使作者的实现比我的更好（FWIW，作者的解决方案是在Java中，我将其转换为Python
－我的解决方案是无法在Java中实现的解决方案）吗？或者，更一般而言，解决该问题需要什么？我采用的方法有什么问题？我假设有一些基本的CS概念（我不熟悉）很重要，可以帮助您选择采用哪种方法来解决此问题。

Answer 1

这是我的写法：

def unique(s):
    return len(set(s)) == len(s)

字符串是可迭代的，因此您可以直接将参数传递给以set()从字符串中获取一组字符（根据定义，该字符将不包含任何重复项）。如果该集合的长度与原始字符串的长度相同，那么您将拥有完全唯一的字符。

您当前的方法还不错，我认为它比作者建议的版本更具Python语言和可读性，但是您应该更改uchars为集合而不是列表。集合具有O（1）隶属关系测试，因此c in uchars如果uchars是集合而不是列表，则平均速度将大大提高。因此，您的代码可以编写如下：

def unique(s):
    uchars = set()
    for c in s:
        if c in uchars:
            return False
        uchars.add(c)
    return True

如果字符串很大并且早期有重复项，这实际上比我的版本更有效，因为它会短路（找到第一个重复项后立即退出）。