Description
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = "leetcode"
输出: false
示例 2：
输入: s = "abc"
输出: true
限制：
- 0 <= len(s) <= 100
- 如果你不使用额外的数据结构，会很加分。
Solutions
0. 问清楚条件
首先应该问下面试官字符串类型，是否只有字母，是什么编码类型，是 ASCII 还是 Unicode。
1. 构建 bool 数组
假设字符串是 ASCII 字符串，采用 bool 数组来操作。
# Time: O(n)
# Space: O(1)
class Solution:
def isUnique(self, astr: str) -> bool:
# Assuming character set is ASCII (128 characters)
if len(astr) > 128:
return False
char_set = [False for _ in range(128)]
for char in astr:
val = ord(char)
if char_set[val]:
# Char already found in astr
return False
char_set[val] = True
return True
2. Bit Manipulation
# Time: O(n^2)
# Space: O(n)
class Solution:
def isUnique(self, astr: str) -> bool:
n = len(astr)
for i in range(n):
for j in range(i+1, n):
if ord(astr[i]) ^ ord(astr[j]) == 0:
return False
return True
3. Bit Manipulation Optimization
假设字符全是字母后，可以这样进行位操作。
variable mark : 0000 0000 0000 0000 0000 0000 0000 0000
mark as : zy xwvu tsrq ponm lkji hgfe dcba
# Time: O(n)
# Space: O(1)
class Solution:
def isUnique(self, astr: str) -> bool:
visited = 0
for ch in astr:
if visited & (b := 1 << (ord(ch) - 97)):
return False
visited |= b
return True
4. 集合
class Solution:
def isUnique(self, astr: str) -> bool:
return len({*astr}) == len(astr)
5. 排序
class Solution:
def isUnique(self, astr: str) -> bool:
s = sorted(astr)
return all(s[i] != c for i, c in enumerate(s[1: ]))