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

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)

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

你目前的方法很好，在我看来，它比作者提出的版本更符合python，可读性更强，但是你应该将uchars改为一个集合而不是一个列表。集合有O（1）成员资格测试，因此如果uchars是集合而不是列表，那么c in 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，或者让它跑得更快，你可以用一套，正如F.J的答案所描述的。

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

（PS，dict是一个内置类型。不要重写它：p.并且string是标准库中的一个模块。）

Answer 3

str = raw_input("Enter string: ")


def isUnique():
    test_dict = dict()
    is_unique = True
    for c in str:
        if(not test_dict.get(c, False)):
            test_dict[c] = c
        else:
            is_unique = False
            break
    if is_unique:
        return "String is unique"
    else:
        return "String is not unique"

print(isUnique())