确定字符串是否包含唯一字符
给定一个字符串string，如果该字符串所有字符唯一则返回True，否则返回False。
例子
has_unique_chars(None) -> False
has_unique_chars("") -> True
has_unique_chars("hello") -> False
has_unique_chars("world") -> True假设
- 字符串字符仅由ascii字符组成
tips
- 统计每个字符的出现次数
- 你能想到不借助额外数据结构的解法吗？
解法
解法1：
def has_unique_chars(string):
if string is None:
return False
return len(set(string)) == len(string)性能：
- 时间复杂度
O(n) - 空间复杂度
O(n)
关键点：
- python中集合(set)的特性:无重复元素
解法2:
def has_unique_chars(string):
if string is None:
return False
chars_set = set()
for char in string:
if char in chars_set:
return False
else:
chars_set.add(char)
return True性能：
- 时间复杂度
O(n) - 空间复杂度
O(n)
关键点：
- python中集合(set)的特性：无重复元素
解法3：
def has_unique_chars(string):
if string is None:
return False
for char in string:
if string.count(char) > 1:
return False
return True性能：
- 时间复杂度
O(n^2) - 空间复杂度
O(1)
关键点：
- String对象的
count方法:统计输入字符在该String对象内出现的次数
解法4：
def has_unique_chars(string):
"""
统计字频判断重复
:param string:
:return:
"""
if string is None:
return False
from collections import Counter
d = Counter(string)
for value in d.values():
if value > 1:
return False
return True性能
- 时间复杂度O(2n)
- 空间复杂度O(n)
关键点
- 利用
Counter统计字符频率：如果字符出现次数大于1，则表示字符串中字符的数量不唯一
解法5：
def has_unique_chars(string):
"""
排序比较相邻是否相同判断重复
:param string:
:return:
"""
if string is None:
return False
al = list(string)
al.sort()
alcount = len(al)
for iter in range(alcount):
if iter + 1 == alcount:
return True
if al[iter] == al[iter + 1]:
return False性能
- 时间复杂度：
O(2n) - 空间复杂度：
O(2n)