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

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()从字符串中获取一组字符(根据定义,它不包含任何重复项).如果该集合的长度与原始字符串的长度相同,那么您将拥有完全唯一的字符.

您当前的方法很好,在我看来,它比作者提出的版本更具Pythonic和可读性,但您应该更改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

如果字符串很大并且早期有重复项,这实际上会比我的版本更有效,因为它会短路(一旦找到第一个副本就退出).

Answer 2

美丽胜于丑陋。

您的方法非常好。这是python，有成百上千种方法可以做某事。（你也更美丽：））。但是，如果您真的希望它更具Python风格和/或使其运行得更快，则可以使用FJ所描述的集合。

第二种解决方案看起来很难理解和理解。

（PS，dict是内置类型。请不要覆盖它：p。并且string是标准库中的模块。）